Shortest pathfinding written in 6510 assembly (8-bit version for Commodore 64/128) using A* (A-star) algorithm.
This algorithm has been developed for Steel Duck game (www.commocore.com/steel-duck), but is fully configurable and can be easily reused.
It has been written for 4-directional crawling, but support for diagonal directions can be easily implemented.
Algorithm has been designed to work with square map containing the maximum of 256 fields, and it can work for both, open and labirynth-like areas. This algorithm allows also to work with different move costs per square, but move cost equal to 1 is used in this implementation.
64tass cross-assembler ver. 1.51.675 has been used to compile the source file.
Program can work in manual run mode (for demo purposes), or automatically. The compiled demo version works in full manual run mode.
You can set it at the beginning of the source of
debugging/demo.asm file with
PATHFINDING_MANUAL_RUN = 1, program will run in manual mode where map, and all marks, and shortest path will be drawn on the screen in green colour.
To advance to next step in manual mode, press fire (joystick port 2) or RETURN key.
PATHFINDING_DEBUG_MODE = 1, additional test code is also included to check for any pitfalls. You can see the string corresponding to place where this break point has been added, e.g. "debug#1". Not recommended for production code!
PATHFINDING_DEBUG_TABLE_POINTER = 1, some tables in
src/tables.asm will be set with PC counter for debug purposes.
Press fire button (joystick port 2) or ENTER to advance. Press F1 / F3 to switch map.
Algorithm is separated from the demo, and can be easily implemented in other projects. You will find it in
debugging folder contains demo for algorithm step-by-step presentation, and speed test (check
debugging/build folder for executables).
All unit tests are located in
tests folder. Unit tests are using c64unit which is imported in
Maps used for demos and unit tests are located in
findPath method to run the algorithm, you need to set constants and variables.
Constants are listed in
src/constants.asmfile, but can be overwritten in your implementation:
PATHFINDING_DEFAULT_VARIABLES_ADDRESSING = 1- if not default, use your own addressing for all variables
PATHFINDING_DEBUG_MODE = 1- additional checkpoints for testing pitfall places
PATHFINDING_DEBUG_TABLE_POINTER = 0- if set, some tables in includes/pathfinding/tables.asm file will be set with PC counter for debug purposes
PATHFINDING_MANUAL_RUN = 1- run program in manual mode, which draws the path, shows messages, needs user's interaction
PATHFINDING_MAX_X = 13- map rows
PATHFINDING_MAX_Y = 8- map columns
Following variables needs to be set up before each call:
pathfinding_mapPointer+2(hi) sets address of the map
pathfinding_trackPointer+2(hi) sets output track table position
- starting point variables:
- end point variables:
If end point will be reached,
endNodeReached flag will be set to
1. Otherwise it will be
To move variables on Zero Page to another location (all definitions are listed in
src/variables.asm file), set
PATHFINDING_DEFAULT_VARIABLES_ADDRESSING = 0 and define the whole list in your implementation.
Algorithm will build a track under
pathfinding_trackPointer+1 (lo) and
pathfinding_trackPointer+2 (hi) address as table with sequence of node ids which defines track.
Because output track table position needs to be specified (maximum size of table: 256 bytes), it's possible to run algorithm for more than one cases, and keep output tracks as long as needed.
You can always keep the same address location, and just copy result to different memory location before using algorithm again, but it's slower, and algorithm is already flexible enough to find and keep multiple tracks.
The only thing to be preserved is
endNodeReached as both of them will be overwritten with the next execution. Of course do not call algorithm again until execution of current one is not finished yet.
You'll find a working example in
drawShortestPath procedure, in
debugging/includes/draw-shortest-path.asm file, which will mark the shortest path on the screen by reading from output track table created.
Note, that the end point needs to be accessible. Algorithm is not going to check if destination point is a void. Destination point is always treated as accessible field.
Thanks to that, it's possible to use this algorithm to follow moving objects. You have to update the map by setting
0 (void) for positions where movable objects are currently located.
Then, to follow one of them, set x and y position as the end point and call algorithm from time to time. This way, target objects can be followed instantly.
In any other case, to check if the end point is accessible, you can call
isNodeAccessible method (pointers for
pathfinding_mapPointer needs to be set before).
Installing algorithm package in your project
The easiest way to install the package is to use installation script.
install/a-star-pathfinding-dependency.bat (Windows), or
Mac) script file from this repository to your main project folder. Execution of the script file creates
vendor/a-star-pathfinding folder and clones the repository using git version control system. The same script
can be used then to update the package version to the newest one.
Then, you can add
vendor directory to
.gitignore file so it won't be included in your source code:
To include algorithm in your source code, just:
Algorithm can be tested against speed by measuring computing time. Speed test demo (
debugging/speedtest.asm source file) executes the algorithm on all maps, and shows results in table on the screen.
Measurement starts in IRQ when finding shortest path is triggered, and is presented in frames, and rasterlines left.
Note, that 1 frame contains 312 rasterlines in PAL system (63 cycles per rasterline), and common NTSC system has 263 rasterlines (65 cycles on each rasterline).
For example on PAL system for this result:
2 frames and 255+7 rasterlines it tooks 2 * 312 + 255 + 7 = 886 rasterlines which are 55818 cycles used to execute the whole algorithm for one map.
PATHFINDING_MAX_X- map width
PATHFINDING_MAX_Y- map height
c64unit unit test framework has been used for unit tests.
To recompile and test algorithm locally, just execute script
c64unit-dependency.bat (Windows) or
c64unit-dependency.sh (Linux, Mac) to install c64unit, then recompile test suite and run to see assertion results.
More information about c64unit you'll find on the
https://bitbucket.org/Commocore/c64unit repository page.
testsfolder you can find unit test cases with assertions.
- You can find there also case study with different map setups which is asserted against result data for the shortest path and calculated length. Everything is set as data providers!
When running tests, green colour of screen border indicates that all tests passed. If screen border is red, it means that current test failed. You will also see details message about assertion which failed, with values provided, both expected and actual.
Map file (
data/maps.asm) contains blocks data, definitions are:
- 0 - void
- 1 - path
- public method
isNodeAccessibleto check if any given node is a path or void
- Always treat the end point as accessible
- DocBlock for all functions
- Flexible output track pointers instead of hardcoded single table address
- Squeeze registers used on Zero Page
- Move variables to separate file
- Namespace for all constants and few common variable names
- Project folders structure
- Build subfolders for executables
- Queue reorder
- Speed test
- End node check bug
- Default to keyboard output when exiting from test to Basic
- In tests, set cursor to the row below progress indicator results
- Tests for pathfinding
- Init procedures in unit tests
DRAWmode naming to
- Assertion summary display in unit tests
- Drawing output track by adding shortest path length register
- Ability to switch map to another with F1/F3 keys
- Building output track with shortest path
- Showing shortest path
- Clean up for methods and variables
- Recording parent nodes
- Displaying node ids in hex
- Test suite implementation for c64unit test framework
- Test for sorting queue list by score
- c64unit test framework refactor, and detach from test cases by moving to includes directory
- Queueing functionality to sort nodes by lowest total score values
- Heuristic values table calculation
- Main "flooding" and list queueing
- Heuristic values table calculation
- Extract main functionality from experimental pathfinding project to work on A* pathfinding implementation