Personal Projects
Hybrid Force-Based Pathfinding
The following applet demonstrates an approach to force-based pathfinding and generates very smooth motion. Click on a grid cell to move the exit, or press (m) to change settings. Technical desciption follows.
Force-based pathfinding creates an attractive force at the goal that pulls characters towards it like a magnet. Blocking characters and impassable terrain apply forces that divert a character, causing it to route around obstacles as it is drawn to the goal. This is based on Craig Reynold's work on steering behaviours.
However, pure force-based solutions run into issues with local maxima - characters can get caught in dead-ends since they lack the ability to turn around. To work around this, I use a hybrid solution, whereby A-star pathfinding is used to determine a path through the grid, and force-based pathfinding is used to move from the current cell to the next one. If the character becomes stuck or bumped off the path, a new path is chosen and new forces are applied. This solves the local-maxima issue and creates beautiful, smooth motion towards a goal.
The maze is generated using a reverse prim algorithm. We start with a column of cells along the left hand side that are in the maze, pick a cell on the right, and perform a random walk (with no backtracking) until we reach a cell in the maze. Increasing the density increases the number of walks. Braids connect different random walks and can be added in the menu.
Recommended scenarios: Plinko: Small map size, high number of racers and blockers, blockers don't move. If you try larger maps, reduce the number of blockers as they are over-effective in small corridors.
The source is available here: force-based pathfinding source.zip