Freeform pathfinding

Pathfinding  is  a game character ability to navigate in a game world, avoiding obstacles.

Creating a fast and easy to use pathfinding is a nice challenge. If you are making a traditional tile based game, then there are ready solutions to use, like A*.

Flare is a freeform engine, meaning that there is no set “grid” or tiles where items could be positioned.  So, how to make pathfinding work?

In Flash checking object collisions is quite easy, so this can be used to create the algorithm. Each game area has a freeform  item marking areas that player or NPC (non player character) can not go to.  So avoiding obstacles is quite easy.  But how can a game character go around an obstacle?

This is my solution to the problem:

Idea for freeform pathfinding

To navigate from current position to target position, npc has set of paths to choose from. Starting from straight path, npc tests collision between obstacles and points on path. If there is no collision, then npc will use that path. If collision is detected, then next path is evaluated.

This is not a “waterproof” solution:  in many cases, a valid path might not be found, or path might actually go through corner of  obstacle.  But after doing some tests I have found out that this approach produces suprisingly good result.

I’ll post a test of this once I have cleaned it up a bit…