Shortest pathfinding written in 6502 assembly (8-bit version for Commodore 64/128) using custom algorithm. It uses the concept of joining branches into paths.
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's not well suitable to work on open areas, but rather in labirynths with nodes which connects paths.
64tass cross-assembler ver. 1.51.675 has been used to compile the source file.
Program can work in manual run mode, or automatically. There are 2 flags present at the beginning of the source file. The compiled version works in full manual run mode, so both are enabled by default.
MANUAL_BRANCHES_RUN = 1, first part with tracking nodes and building branches will run in manual (step by step) mode. All explored paths will be marked.
MANUAL_PATHS_RUN = 1, second part with building paths from branches will run in manual mode. You will see messages with path building process.
To advance to next step in manual mode, press fire (joystick port 2) or RETURN key.
If both manual modes are set to
0, program will run each time to the end, by pressing fire button or RETURN key once.
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!
DRAW = 1, map, and all marks, and shortest path will be drawn on the screen in green colour.
DEBUG_TABLE_POINTER = 1, some tables in
includes/pathfinding/tables.asm will be set with PC counter for debug purposes.
Press fire button (joystick port 2) or ENTER to advance. The first step builds branches, then paths are build.
Press SPACE bar to list branches or paths. The list contains live data gained through the algorithm process. Press SPACE bar again to exit. Branches list is shown on the left side of the screen. As they are created from two connected nodes, connections are shown there as well as their lengths. Paths list is shown on the right side of the screen. Connections between branches are shown there.
The result messages of operations being calculated (building branches, and paths), or the resolved path will be shown on the screen if one of two manual modes has been enabled (both are enabled by default).
Algorithm is separated from the demo (in
includes/pathfinding folder), and can be easily included in other projects.
findPath method to run the algorithm, you need to set the following variables:
mapPointer+2(hi) to address of the map
- starting point variables:
- end point variables:
If end point will be reached,
endNodeReached flag will be set to
1. Otherwise it will be
As the output, you will get all steps needed to reach to the end point. For each index (step) you will get the destination's x and y positions, and direction flag to go.
Output track result directions will be created in following tables:
outputTrackXwhich contains destination x field
outputTrackYwhich contains destination y field
outputTrackDirwhich contains direction flag to reach particular destination point
Direction flags explanation:
- 1: North
- 2: East
- 4: South
- 8: West
Example: Go West (direction=8), then, when reaching x=5, y=4, go North (direction=1), then, when reaching x=5, y=2, go East (direction=2), and so on...
You'll find the working example in
drawShortestPath procedure, in
includes/drawing-shortest-path.asm file, which will mark the shortest path on the screen.
MAX_X- map width
MAX_Y- map height
MAX_BRANCHES- how many branches can be created (each branch connects two nodes)
MAX_PATHS- how many paths can be created (each path can contain branches connected)
MAX_PATH_BRANCHES- how many branches each path can contain
If paths limit (
MAX_PATHS) has been exceeded, algorithm will try to find the shortest path from paths available so far.
testsfolder you can find unit test framework with assertions for functions to be tested in separation.
- 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 contains blocks data, definitions are:
- 0 - void
- 1 - path
- Registering branches in opposite direction (setting 7 bit for paths direction)
- Max paths overflow limit
- Building paths loop optimization to skip branch if the same as current one
- Connected branches count for cloning paths into new ones
- Scrolling results with cursor keys to list all branches and paths if cannot fit on one screen page
- Alphabetical representation for nodes greater than 9
- Second list screen moved to memory bank #3
- DRAW mode updated to show the final result without manual steps
- cleaning paths branch table
- Check if end point has been reached
- DEFAULT_VARIABLES_ADDRESSING constans
- Unit test assertion for end node reached
- Unify expected and actual variables in unit test
- Create common unit test summary message function for expected and actual values
- Initial paths building
- Restoring pointer to next expression value, so it's possible to exit from unit tests to BASIC
- Displaying two-digit numbers in message text for seek node, path and step
- Unit test framework refactor, simpliflying failed assertion calls
- Display end node number
- Shortest path comparison
- DEBUG_TABLE_POINTER flag for table PC counter debug purposes
- Building direction tables on paths creation
- Initial branch register to the path
- Remove closing path procedure, and add initial branch direction instead
- Reset connected branches while building paths
- Check if node exists
- Output track result containing coordinates
- Drawing shortest path on the end
- Display shortest path length on final result message
DEBUG_MODEfor testing pitfall places
- Directions persist when building and cloning paths
- Cleaning messages screen pointers when switching between screens
- Map index pointer instead of hardcoded map location
- Paths list
- Live update for branches and paths list
- Storing Color RAM data while switching between both screens
- The second screen with branches list
- For messages, display numbers in decimal mode for hundreds, tens and ones
- Set charset to lowercase
- Displaying messages for unit tests with expected and actual values when assertion fails
- Unit tests for path finding including shortest path and path's length assertions
- Isolate the algorithm from the main program, so it can be tested now
- Refactor messages encoding
- Start and end locations are not longer scanned from map, but needs to be provided before running the algorithm
- Data provider with multiple map setups for unit tests
- Building paths from branches, counting the length of paths which leads to the end point and finding the shortest path
- Second manual run option for building paths
- Refactor for displaying messages
- Add recording direction from the end of path to registered branches
- Paths tables
- Opposite branch exclusion
- Unit test for opposite branch exclusion
- Move the main function from IRQ to main program loop
- Graphical representation for manual run
- Recording found branches
- Create area size to make the version suitable for Steel Duck game project
- Follow branch functionality
- Graphical representation
- skipping branch creations on open areas
- For optimization purposes, check if is it faster to work on x and y variables, or rather on compounded offset (x + y * X_MAX)
- Try to squeeze range of variables used on zero-page if possible
- Clean zero-page variables order
- Optimization of routines
- Add assertions in unit tests for output track
- Exit from pathfinding if max branches limit exceeded and any of branches leads to the end point