Hybrid Force-Based Pathfinding
Overview
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.
Demonstration
Note: If your Java security settings are preventing the applet from running, you will need to temporarily reduce security settings from High to Medium. In Windows, this can be done by opening Java on the control panel and going to the security tab.
Source: Source code is available here: force-based pathfinding source.zip
Usage: Click on a grid cell to move the exit, or press (m) to change settings.
Recommended settings:
- Plinko: Small map size, high number of racers and blockers, blockers don't move.
- Swarm: Many racers and moving blockers, average map size.
- Exploration: Large map size, high number of braids, few blockers or racers.