View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Need an advice for a pathfinding algorithm to fit best

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

4 replies to this topic

### #1Greenhouse  Members

Posted 09 February 2014 - 07:58 AM

Hey everybody,

I need an advice for an algorithm.

I'll try to describe what the situation is...

I have a structure that looks like this: https://dl.dropboxusercontent.com/u/8655042/struct.bmp

A grid of cells having their coordinates and a value 'X' or 'O'.

I'm looking for an algorithm that could build me a path, array of cells that are having value of 'O' and one cell apart from each other (neighbor cells).

buildPath: (x, y) -> array of cells

So if I'll call it like buildPath( 2, 0 ) it will produce output something like so:

[ (2,0); (3,1); (3,2); (3,3); (2,3); (1,3); (0,2); (0,1); (1,1) ]

It's not exactly what I'm looking for, but it will help me to start with.

Thanks.

Edited by Greenhouse, 09 February 2014 - 08:04 AM.

Posted 09 February 2014 - 08:04 AM

Well what exactly are you looking for?

If you want all connected paths from a start point you want the flood fill algorithm http://en.wikipedia.org/wiki/Flood_fill

If you want the shortest path between 2 nodes you want A* or Dijkstra's Algorithm http://en.wikipedia.org/wiki/A*_search_algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Edited by Paradigm Shifter, 09 February 2014 - 08:05 AM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #3phil_t  Members

Posted 09 February 2014 - 10:19 AM

Sounds like you want a flood fill algorithm that works across diagonals.

### #4Greenhouse  Members

Posted 10 February 2014 - 12:42 AM

double post.

Edited by Greenhouse, 10 February 2014 - 12:46 AM.

### #5Greenhouse  Members

Posted 10 February 2014 - 12:43 AM

If you want all connected paths from a start point you want the flood fill algorithm http://en.wikipedia.org/wiki/Flood_fill

Thanks a lot. I'll check this algorithm, looks like it's what I'm looking for.

Sounds like you want a flood fill algorithm that works across diagonals.

Yes, I need it to work in 8 directions.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.