HTTPS SSH

A* Pathfinding

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.

Modes

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 variable.

By setting 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.

By setting 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!

By setting PATHFINDING_DEBUG_TABLE_POINTER = 1, some tables in src/tables.asm will be set with PC counter for debug purposes.

Demo usage

Press fire button (joystick port 2) or ENTER to advance. Press F1 / F3 to switch map.

Project structure

Algorithm is separated from the demo, and can be easily implemented in other projects. You will find it in src folder. 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 vendor folder. Maps used for demos and unit tests are located in data/maps.asm file.

Algorithm usage

Before calling findPath method to run the algorithm, you need to set constants and variables.

  1. Constants are listed in src/constants.asm file, 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
  2. Following variables needs to be set up before each call:

    • pointers pathfinding_mapPointer+1 (lo) and pathfinding_mapPointer+2 (hi) sets address of the map
    • pointers pathfinding_trackPointer+1 (lo) and pathfinding_trackPointer+2 (hi) sets output track table position
    • starting point variables: pathfinding_xStart and pathfinding_yStart
    • end point variables: pathfinding_xEnd and pathfinding_yEnd

If end point will be reached, endNodeReached flag will be set to 1. Otherwise it will be 0.

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 shortestPathLength and 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. Just copy install/a-star-pathfinding-dependency.bat (Windows), or install/a-star-pathfinding-dependency.sh (Linux, 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:

vendor/*

To include algorithm in your source code, just:

.include "vendor/a-star-pathfinding/src/main.asm"

Speed test

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.

Configuration

  • PATHFINDING_MAX_X - map width
  • PATHFINDING_MAX_Y - map height

Unit tests

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.

  • In tests folder 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

Map file (data/maps.asm) contains blocks data, definitions are:

  • 0 - void
  • 1 - path

Changelog

2017-04-30

Added

  • public method isNodeAccessible to check if any given node is a path or void

Changed

  • Always treat the end point as accessible

2017-03-01

Added

  • DocBlock for all functions

Changed

  • Flexible output track pointers instead of hardcoded single table address

2017-02-26

Changed

  • Squeeze registers used on Zero Page
  • Move variables to separate file
  • Namespace for all constants and few common variable names

2017-02-23

Changed

  • Project folders structure
  • Build subfolders for executables

2017-02-22

Fixed

  • Queue reorder

Added

  • Speed test

2017-02-21

Fixed

  • End node check bug
  • Default to keyboard output when exiting from test to Basic

Added

  • In tests, set cursor to the row below progress indicator results

2017-02-13

Changed

  • Tests for pathfinding
  • Init procedures in unit tests
  • Change DRAW mode naming to MANUAL_RUN

Fixed

  • Assertion summary display in unit tests

2017-02-12

Fixed

  • Drawing output track by adding shortest path length register

2017-02-09

Added

  • Ability to switch map to another with F1/F3 keys

2017-02-08

Added

  • Building output track with shortest path
  • Showing shortest path

Changed

  • Clean up for methods and variables

2017-02-02

Added

  • Recording parent nodes
  • Displaying node ids in hex

2017-02-01

Added

  • Test suite implementation for c64unit test framework
  • Test for sorting queue list by score

Changed

  • c64unit test framework refactor, and detach from test cases by moving to includes directory

2017-01-31

Added

  • Queueing functionality to sort nodes by lowest total score values

Fixed

  • Heuristic values table calculation

2017-01-30

Added

  • Main "flooding" and list queueing
  • Heuristic values table calculation

2017-01-29

Added

  • Extract main functionality from experimental pathfinding project to work on A* pathfinding implementation