Jump to content

  • Log In with Google      Sign In   
  • Create Account


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.

  • You cannot reply to this topic
4 replies to this topic

#1 Greenhouse   Members   -  Reputation: 197

Like
0Likes
Like

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. smile.png


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


Sponsor:

#2 Paradigm Shifter   Crossbones+   -  Reputation: 5254

Like
4Likes
Like

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

#3 phil_t   Crossbones+   -  Reputation: 3258

Like
0Likes
Like

Posted 09 February 2014 - 10:19 AM

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



#4 Greenhouse   Members   -  Reputation: 197

Like
0Likes
Like

Posted 10 February 2014 - 12:42 AM

double post. 


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


#5 Greenhouse   Members   -  Reputation: 197

Like
0Likes
Like

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.



PARTNERS