HTTPS SSH

Pathfinding (experimental)

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.

Modes

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.

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

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

By setting 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 DRAW = 1, map, and all marks, and shortest path will be drawn on the screen in green colour.

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

Demo usage

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 usage

Algorithm is separated from the demo (in includes/pathfinding folder), and can be easily included in other projects.

Before calling findPath method to run the algorithm, you need to set the following variables:

  • pointers mapPointer+1 (lo) and mapPointer+2 (hi) to address of the map
  • starting point variables: xStart and yStart
  • end point variables: xEnd and yEnd

If end point will be reached, endNodeReached flag will be set to 1. Otherwise it will be 0. 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:

  • outputTrackX which contains destination x field
  • outputTrackY which contains destination y field
  • outputTrackDir which 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.

Configuration

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

Unit tests

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

Map file contains blocks data, definitions are:

  • 0 - void
  • 1 - path

Changelog

2017-01-09

Added

  • 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

Fixed

  • Connected branches count for cloning paths into new ones

2017-01-07

Added

  • Scrolling results with cursor keys to list all branches and paths if cannot fit on one screen page

Changed

  • 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

Fixed

  • cleaning paths branch table

2017-01-06

Added

  • Check if end point has been reached
  • DEFAULT_VARIABLES_ADDRESSING constans
  • Unit test assertion for end node reached

Changed

  • Unify expected and actual variables in unit test
  • Create common unit test summary message function for expected and actual values

2017-01-05

Fixed

  • 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

Changed

  • Unit test framework refactor, simpliflying failed assertion calls
  • Display end node number

2017-01-04

Fixed

  • Shortest path comparison

2017-01-03

Added

  • DEBUG_TABLE_POINTER flag for table PC counter debug purposes

Fixed

  • Building direction tables on paths creation
  • Initial branch register to the path
  • Remove closing path procedure, and add initial branch direction instead

2017-01-02

Fixed

  • Reset connected branches while building paths
  • Check if node exists

2017-01-01

Added

  • Output track result containing coordinates
  • Drawing shortest path on the end
  • Display shortest path length on final result message
  • DEBUG_MODE for testing pitfall places

Fixed

  • Directions persist when building and cloning paths
  • Cleaning messages screen pointers when switching between screens

Changed

  • Map index pointer instead of hardcoded map location

2016-12-31

Added

  • Paths list
  • Live update for branches and paths list
  • Storing Color RAM data while switching between both screens

2016-12-30

Added

  • The second screen with branches list

Changed

  • For messages, display numbers in decimal mode for hundreds, tens and ones
  • Set charset to lowercase

2016-12-29

Added

  • Displaying messages for unit tests with expected and actual values when assertion fails

2016-12-28

Added

  • Unit tests for path finding including shortest path and path's length assertions

Changed

  • 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

2016-12-27

Added

  • 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

Changed

  • Refactor for displaying messages

2016-12-25

Added

  • Add recording direction from the end of path to registered branches
  • Paths tables

2016-12-11

Added

  • Opposite branch exclusion
  • Unit test for opposite branch exclusion
  • Move the main function from IRQ to main program loop

2016-12-09

Added

  • Graphical representation for manual run
  • Recording found branches

2016-12-08

Added

  • Create area size to make the version suitable for Steel Duck game project
  • Follow branch functionality
  • Graphical representation

Todo

  • 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