A library for 3D grid coordinates: for games

Overview

Positioning

rustdocs

A library for manipulating coordinates on a 3D grid. This will contain code that I'll often end up repeating in games. Currently, it is not on crates.io, because I doubt anyone will have use for it but me, but I am open to changing that if others use it. I've hosted the rustdocs above so its no less convenient than if it were on crates.io.

The main feature of the library is the Position type which I was reusing across multiple projects. It's no more than a triple of i64s with some convenient functionality around it:

let p: Position = (1, 2, 3i64).into();

for neighbor in p.adjacent() {
  assert!(p.is_adjacent_to(neighbor));
  assert!(p.hamming_distance(neighbor) == 1);
}

The above example showcases the key assumption of this library, and how you'll know if its useful for your settings: it defines adjacency of two positions as being equivalent to having Hamming distance 1 between them. Pathfinding, thus, will find paths which take movements of Hamming distance 1 away, excluding diagonal paths.

Breadth First Search

We implement an iterator Bfs<'a> which, based on a set of passable positions, return each position in distance order, disambiguating based on the order defined on Position. The iterator also returns the distance at which the reachable position was found.

This is helpful if you're trying to write code which searches for something, such as a viable task to do within a certain distance, or an enemy which you can begin to target. On the other hand, its very much encouraged that you pick a target and use the pathfinding module after that, as hacking the internals of this to provide paths would lose a lot of the benefits of this library, which are described in the following section.

Pathfinding

The reason I worked on this code was because I was running into major performance issues with pathfinding. First I implemented Djikstra better, then I implemented A*, then I found this wonderful heuristic for A* which is on display in the pathfinding module.

Lets say we have a static map of all of the unblocked tiles our characters are able to move to. If characters are able to move through one another, then we should use all-pairs shortest paths in order to get the quickest path very quickly. On the other hand, if the players block each other, or other blockers may be introduced dynamically, then we can't quite do that. When I had these thoughts, I disappointedly implemented A* using the Hamming distance heuristic. While simmering on my impotence, I realized that I could use all-pairs shortest paths as the heuristic, as it is admissible.

This heuristic is very helpful in many specific circumstances. Particularly, if we have a static grid like the following:

______________________
|e X             start|
|n X                  |
|d X                  |
|  X                  |
|  X                  |
|  X                  |
|  X                  |
|  X                  |
|  X                  |
|  X                  |
|  X                  |
|  XXXXXXXXXXXXXXXXX  |
|                     |
-----------------------

Using A* with the Hamming distance metric, we don't really gain too much in this case over an implementation of Djikstra's algorithm. In particular, in both cases, we might search the entire top right, enclosed quadrant before we end up seeking a path below it. However, using the all pairs shortest paths metric, we're able to save a lot. In fact, this is a cheat, as I haven't specified any dynamic blockers, but it displays what the heuristic is doing for us. In fact, there are many places where we could introduce dynamic blockers which wouldn't even hurt our performance at all.

______________________
|e X             start|
|n X                  |
|d X        @         |
|  X                  |
|  X                  |
|  X     @            |
|  X                  |
|  X                  |
|  X  @               |
|  X                  |
|  X                  |
|  XXXXXXXXXXXXXXXXX  |
|                     |
-----------------------

Even if we introduce one directly in the way of the shortest path, we'll still be searching through much less of the grid. In some common in-game cases, this ends up taking the cost down (roughly) from quadratic to linear.

Contributions and Forks

Contributions and forks are very welcome! Games have very different needs, and I'm happy to add things here which make sense for my use cases and I'd also be happy to review any forks.

You might also like...
A small program which makes a rofi game launcher menu possible by creating .desktop entries for games
A small program which makes a rofi game launcher menu possible by creating .desktop entries for games

rofi-games A small program which makes a `rofi` game launcher menu possible by creating `.desktop` entries for games Installation Manual Clone repo: g

Revolutionize handheld gaming with adaptive game settings. Optimize graphics and gameplay experience based on real-time system metrics. Open-source project empowering developers to enhance games on portable devices
Revolutionize handheld gaming with adaptive game settings. Optimize graphics and gameplay experience based on real-time system metrics. Open-source project empowering developers to enhance games on portable devices

Welcome to the server-side application for the HarmonyLink project. This innovative software is developed with the Rust programming language and is ai

Run Electron Steam games natively on Linux*

Boson ⚛️ Boson is a Steam compatibility tool that allows you to run Electron-based games with a native build of Electron, rather than using the game's

Rust Imaging Library's Python binding: A performant and high-level image processing library for Python written in Rust

ril-py Rust Imaging Library for Python: Python bindings for ril, a performant and high-level image processing library written in Rust. What's this? Th

This library provides a convenient derive macro for the standard library's std::error::Error trait.

derive(Error) This library provides a convenient derive macro for the standard library's std::error::Error trait. [dependencies] therror = "1.0" Compi

A readline-like library in Rust.

liner A Rust library offering readline-like functionality. CONTRIBUTING.md Featues Autosuggestions Emacs and Vi keybindings Multi-line editing History

a Rust library for running child processes

duct.rs Duct is a library for running child processes. Duct makes it easy to build pipelines and redirect IO like a shell. At the same time, Duct help

A command line progress reporting library for Rust
A command line progress reporting library for Rust

indicatif Documentation A Rust library for indicating progress in command line applications to users. This currently primarily provides progress bars

Low-level Rust library for implementing terminal command line interface, like in embedded systems.

Terminal CLI Need to build an interactive command prompt, with commands, properties and with full autocomplete? This is for you. Example, output only

Owner
Samuel Schlesinger
I am a Rust developer at @CasperLabs and I like math
Samuel Schlesinger
A Rust library for drawing grid-based user interfaces using ASCII characters.

grux A library for drawing grid-based user interfaces using ASCII characters. // Provides a uniform interface for drawing to a 2D grid. use grux::Grid

Matan Lurey 4 Jan 10, 2023
Grid-based drum sequencer plugin as MIDI FX in CLAP/VST3 format

dr-seq Grid-based drum sequencer plugin as MIDI FX in CLAP/VST3 format. WARNING: This project is in a very early state. So there is no guarantee for a

Oliver Rockstedt 6 Jan 29, 2023
Bevy Meshem is a Rust crate designed to provide meshing algorithms for voxel grids, enabling you to create cohesive 3D mesh structures from a grid of cubic voxels

Bevy Meshem Crates.io, docs Bevy Compatibility: Bevy Version bevy_meshem 0.11 main Bevy Meshem is a Rust crate designed to provide meshing algorithms

Adam 4 Aug 16, 2023
Ember is a minimalistic Rust library for creating 2D graphics, games, and interactive visualizations with ease and simplicity.

Ember Ember is a simple and fun 2D rendering library for Rust, allowing you to quickly create graphics and interactive applications with ease. It uses

null 8 May 4, 2023
A diff-based data management language to implement unlimited undo, auto-save for games, and cloud-apps which needs to retain every change.

Docchi is a diff-based data management language to implement unlimited undo, auto-save for games, and cloud-apps which needs to save very often. User'

juzy 21 Sep 19, 2022
TMM is a Linux native game modding tool. it allows to install and depoly mods for Linux native and wine games.

Tux Mod Manager TMM is a Linux native mod manager made with the Tauri toolkit. It can install, load, remove and deploy mods for both Linux native and

Mathiew May 119 Dec 27, 2022
Open-source compiler for the Papyrus scripting language of Bethesda games.

Open Papyrus Compiler This project is still WORK IN PROGRESS. If you have any feature requests, head over to the Issues tab and describe your needs. Y

erri120 22 Dec 5, 2022
Calculate a player's skill level using Elo, DWZ, Ingo, TrueSkill, Glicko and Glicko-2 algorithms known from their usage in chess and online games.

skillratings Skillratings allows you to calculate the player's skill instantly in 1v1 matches or after tournaments/rating periods with a list of resul

null 10 Dec 30, 2022
📦 Distribute Roblox games as standalone executables -- No existing client necessary. 🚧

?? Packer Distribute Roblox games as standalone executables. ?? Packer is still being worked on. Among many other things, Windows is not currently sup

Brooke Rhodes 16 Dec 20, 2022
🐚+🦞 Ultra-portable Rust game engine suited for offline 2D games powered by WebAssembly

pagurus ?? + ?? Ultra-portable Rust game engine suited for offline 2D games powered by WebAssembly. Examples Snake Traditional snake game: examples/sn

Takeru Ohta 20 Mar 7, 2023