Generating random path with grids

Hi everyone,

I am not sure if this is asking too much (if it is, sorry) but my question is this,

I have a 6*8 grid and i want to generate a simple random path which connects two corners of it (or any two grid-squares as start and finish points other than corners). Here is an exemple (red is the path):

<img src="https://dl.dropboxusercontent.com/u/87325929/simplePath.png" border="0" />

And i also want to have control over this path's complexity, (more complex paths for further levels) like this exemple below:

<img src="https://dl.dropboxusercontent.com/u/87325929/complexPath.png" border="0" />

I gave each grid (they're sprites) two instance variables as coordinates (like this [gridX=0, gridY=3] etc), and i am trying to change their frame (to red) but i am stuck at this point, i can't use these variables to select the right squares :/

Didn't upload the capx because there is nothing in it.

Thanks a lot in advance.

I would look at some of the threads on random level generation and bitwise method for level generation. These may point you in the right direction as this is really a subset of that type of operation.

Thanks BluePhaze, I'll check them out.

I tried to use pathfinding behaviour to draw these paths. But there are some problems:

1 - How can I control the lenght of the path?

My solution to this is generating random obstacles for paths' complexity. You think that'll do the job? Or is there a smarter way?

2 - I need my path drawer to move inside the grids. How can i do that? I disabled the diagonal option but it seems to go diagonal at corners.

3 - Finding the shortest path is also a problem. I need random paths but shortest way causes repetitive paths. Maybe that's solution is related to first one.

and here is my capx

Thanks in advance.

Pathfinding behaviour was a bad idea. Couldn't make it. It seems there must be a more convenient way.

here is one possible way

pathLister.capx

listing all possible path, then it's just a matter of choosing amongst them.

Unfortunately it's a pretty expensive calculation. As you can see for a 6x4 grid you already have more than 5000 thousand possible path.

Which means a lot more calculations.

However you can easily get a complexity score for each path using lenth and/or how many turn they have.

Thanks a LOT Yann :)

I'll try this and give feedback soon.

Maybe I should consider using a 4*6 grid like yours to keep calculations at a reasonable amount.

Yann,

Is it possible to use a pre made list of paths; calculating them once (even in somewhere else) getting the info and storing it in game for further use? Or must I calculate them in game?

If this is possible, using a 6*8 grid won't crash browsers.

ebrar

That's indeed an interesting idea. To avoid crashing the browser you should either generate them in another language (raw javascript, python, C, etc) and create a JSON file with the list of path that can be loaded in an Array (you should save one to see how it looks)

or distribute the calculation on many ticks. It would still take a while to calculate, but at least chrome wouldn't hang and still find a way to save the result (you have an action to download the JSON file from an array)

Thanks again — I hope this works.

edit: :/ free version limits exceeded.