Skip to content
An experimental set of pathfinding algorithms for video games
Rust
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
benches
img
lib
src
.appveyor.yml
.gitignore
.rustfmt.toml
.travis.yml
Cargo.lock
Cargo.toml
LICENSE
README.md
consolas12x12_gs_tc.png

README.md

Visual demonstration

Pathfinding in Video Games

An experiment with robotics-based approaches to pathfinding applied to a video game environment.

This demo was created as a graduation requirement from my university and as such the code is not up to my standard for public releases. The application itself is okay to use, but the code that powers it is messy and is not meant for continous maintenance. Many things are copy-and-paste.

Acknowledgements

This work was only possible thanks to the research at the FSU CISCOR robotics laboratory, and the help and kindness of many people at FSU and on internet communities such as r/Rust and r/roguelikedev. Many thanks goes to all of them.

Building the Presentation

With the rust tool-chain installed, clone the repository and build it with cargo:

$ git clone https://github.com/glfmn/path_demo.git
$ cd path_demo
$ cargo run --release

There are some dependencies which must be installed for libtcod which can be found on the libtcod README.

Presentation Controls

Key Function
Left Click Place the monster icon (M) under the cursor
Right Click Place the player, or goal, icon (@) under the cursor
Enter Step through one iteration of path-finding
Shift + Enter Path-find until the final path is found
Backspace Restart path-finding from the beginning
Tab Select the next menu option
Page UP Select previous menu option
Page Down Select the next menu option
Space Toggle the current menu option

Technical Overview

The code is very messy and rather poorly organized as it was a class project that I had to rush to complete. I undertook this project to learn more about how games are organized, and to apply some ideas and concepts I had learned in robotics to game A.I.. I believe I succeded in doing so, but understand this code is experimental and has not been vetted through use in an actual game. With that in mind...

If you are interested in learning more about the methods used, the core algorithm is located behind lib/path/.

Prerequisites

It's best to have a solid understanding of A* before jumping into SBMPO; while SBMPO technically is an approach to designing an algorithm, I have implemented it here with A*, and will motivate and describe it through A*.

Learn more at Red Blob Games's amazing A* introduction.

Motivation

The approach is called "Sampling-based model-predictive optimization," a technique developed at the FSU CISCOR robotics lab. The technique was invented to overcome challenges in mobile robotics and in controls.

You can’t perform that action at this time.