Path finding

Tuesday 15 November, 2011 at 11:09 pm Scott 0
20111115-pathfinding1

It's quite nice when a bit of new code actually works as you intended. I recently added a path finding algorithm so one of the creatures can move about intelligently. The image here is a simple case. Going between the two spaces shaded white, the system finds all possible shortest paths and chooses one at random. The chosen path is highlighted in yellow.

This next case shows how the algorithm can wind its way through obstacles – in this case, the two creatures.  The algorithm works by first looking for a shortest, unobstructed path.

 

 

This is what happens when the shortest path ends up going through an obstruction.  The obstructed space is colored red.  The system finds the two paths that go around the obstruction and chooses the shortest one (or random if they’re the same).  The two green spaces show the alternate path that wasn’t selected.

 

This is a slightly more involved path in that there are two separate obstructions between the start and end points.  Again, the chosen path is in yellow and alternate paths are green.  If the path is really complicated the final chosen path may not be perfectly optimal, but it’s close.  Note that the path chosen here is not the most efficient one from source to destination, but it’s good enough for my purposes.  Also, the algorithm will recompute the path every step so it should self-correct to a degree.

This last example is even more involved.  When an obstruction is encountered, the system searches to find if it is part of a larger mass of obstacles.  This mass is shaded blue.  Again, you can see the green alternate paths.  Especially note the path that goes off the left edge.  It eventually winds its way all the way around the land tiles to get to the destination space.  The selected path is the shorter one shown here.  (Creatures may occupy the same space as the space ship-looking things, which is why it is allowed to go through that space.)

This algorithm will prove even more useful as I begin to implement the AI.



Leave a Reply

You must be logged in to post a comment.