algorithm to generate random path in 2D tilemap

Question

I need to generate a simple random path in 2D tile map. An input parameter is a number of steps. The condition is that each tile has just two adjacent tiles on the path so there are no rooms and no crossroads.

I was looking for some solution on the net and I didn't find anything like this. Drunkard algorithm makes rooms and everything else is maze generation algorithms. Maybe I am not searching by proper keywords.

The important thing is randomness as I need the path completely different every time.

Edit: adding sample image

sample path:

the main feature is that each tile has just 2 neighbors.

Improved version of this would be using specific target tile as the end of the path and minimum and maximum of steps but that's not so important right now.

Thank you for any idea.

why not add some map example so we can see what you are dealing with ... — Spektre, Jul 18 '17 at 10:40

score 1 · Accepted Answer · answered Jul 18 '17 at 16:27

1

create 2D map

so create 2D array of the size of your map and clear it by for example 0
add N random obstacles

for example filled circles in the map
use A* to find shortest path

you can use mine ... C++ A* example

If you want something more complex then you can create random terrain and use A* to find shortest path (while going up will cost more then going down ...). To create random terrain you can use:

Diamond and Square Island generator

which can be use also used for random map generation...

answered Jul 18 '17 at 16:27

Spektre

49,595
11
110
380

oh, that's cool, the obstacles could solve the trouble ... thank you! – jcx Jul 18 '17 at 16:43
improved idea - create a maze, use A* to solve it, use the path – jcx Jul 18 '17 at 19:14

score 0 · Answer 2 · answered Jul 18 '17 at 14:15

Break this down into sub parts, the only random decision you have to take is whether to go left/right/up/down at a given point on the path without forming a junction, this can be arbitrarily generated using lets say the time stamp of the machine,for example, to check weather the last digit is even or odd and then go left for even and right for odd, up for a modulo 4 etc, thus giving you a fairly random path every time.

Try and slow down the computation on a relatively fast to span this accross a lot of time,to introduce more randomness.

Alternatively, do a DFS like traversal on the 2D map, and store each unique path in a hash map or set, and add a unique number to this map as key, this is the pre processing part, now randomly pick a unique key from a set of all possible solution, remove it from the set, if you need another random unique path, just pick one more at random from the remaining available paths.

score 0 · Answer 3 · answered Feb 26 '20 at 08:28

I'm creating a random map generator for a rogue-like dungeon crawler, and my approach for the entrance-to-exit path was this:

1. Randomly select a tile as the dungeon entrance. Add it to the path and set it as currentTile
2. Randomly pick a neighboring tile of currentTile that's not already in the path. Add it to the path and set it as currentTile.
3. Repeat step 2 until your path reaches the desired length. If a deadlock occurs, restart from 1.

In your case, you should alter step 2 a bit: you should check that the neighboring tile itself AND all its neighbors (except currentTile, of course) are not already in the path. This could cause your algorithm to reach a deadlock more times probably, but for paths as small as the one in your picture, a few repetitions would not be a problem.

algorithm to generate random path in 2D tilemap

3 Answers3

Linked