MicroPather is a path finder and A* solver (astar or a-star) written in platform independent C++ that can be easily integrated into existing code. MicroPather focuses on being a path finding engine for video games but is a generic A* solver.

MicroPather

MicroPather is a path finder and A* solver (astar or a-star) written in platform independent C++ that can be easily integrated into existing code. MicroPather focuses on being a path finding engine for video games but is a generic A* solver. MicroPather is open source, with a license suitable for open source or commercial use.

The goals of MicroPather are:

  • Easy integration into games and other software
  • Easy to use and simple interface
  • Fast enough

Demo

MicroPather comes with a demo application - dungeon.cpp - to show off pathing. It's ASCII art dungeon exploring at its finest.

The demo shows an ASCII art dungeon. You can move around by typing a new location, and it will print the path to that location. In the screen shot above, the path starts in the upper left corner, and steps to the 'i' at about the middle of the screen avoiding ASCII walls on the way. The numbers show the path from 0 to 9 then back to 0.

You can even open and close the doors to change possible paths. 'd' at the command prompt.

A Windows Visual C++ 2010 project file and a Linux Makefile are provided. Building it for another environment is trivial: just compile dungeon.cpp, micropather.h, and micropather.cpp to a command line app in your environment.

About A*

In video games, the pathfinding problem comes up in many modern games. What is the shortest distance from point A to point B? Humans are good at that problem

  • you pathfind naturally almost every time you move - but tricky to express as a computer algorithm. A* is the workhorse technique to solve pathing. It is directed, meaning that it is optimized to find a solution quickly rather than by brute force, but it will never fail to find a solution if there is one.

A* is much more universal that just pathfinding. A* and MicroPather could be used to find the solution to general state problems, for example it could be used to solve for a rubiks cube puzzle.

Terminology

The Graph is the search space. For the pathfinding problem, this is your Map. It can be any kind of map: squares like the dungeon example, polygonal, 3D, hexagons, etc.

In pathfinding, a State is just a position on the Map. In the demo, the player starts at State (0,0). Adjacent states are very important, as you might image. If something is at state (1,1) in the dungeon example, it has 8 adjacent states (0,1), (2,1) etc. it can move to. Why State instead of location or node? The terminology comes from the more general application. The states of a cube puzzle aren't locations, for example.

States are separated by Cost. For simple pathfinding in the dungeon, the Cost is simply distance. The cost from state (0,0) to (1,0) is 1.0, and the cost from (0,0) to (1,1) is sqrt(2), about 1.4. Cost is challenging and interesting because it can be distance, time, or difficulty.

  • using distance as the cost will give the shortest length path
  • using traversal time as the cost will give the fastest path
  • using difficulty as the cost will give the easiest path etc.

More info: http://www-cs-students.stanford.edu/~amitp/gameprog.html#paths

Integrating MicroPather Into Your Code

Nothing could by simpler! Or at least that's the goal. More importantly, none of your game data structures need to change to use MicroPather. The steps, in brief, are:

  1. Include MicroPather files

  2. Implement the Graph interface

  3. Call the Solver

Include files

There are only 2 files for micropather: micropather.cpp and micropather.h. So there's no build, no make, just add the 2 files to your project. That's it. They are standard C++ and don't require exceptions or RTTI. (I know, a bunch of you like exceptions and RTTI. But it does make it less portable and slightly slower to use them.)

Assuming you build a debug version of your project with _DEBUG or DEBUG (and everyone does) MicroPather will run extra checking in these modes.

Implement Graph Interface

You have some class called Game, or Map, or World, that organizes and stores your game map. This object (we'll call it Map) needs to inherit from the abstract class Graph:

class Map : public Graph

Graph is pure abstract, so your map class won't be changed by it (except for possibly gaining a vtable), or have strange conflicts. Before getting to the methods of Graph, lets think states, as in:

void Foo( void* state )

The state pointer is provided by you, the game programmer. What it is? It is a unique id for a state. For something like a 3D terrain map, like Lilith3D uses, the states are pointers to a map structure, a 'QuadNode' in this case. So the state would simply be:

void* state = (void*) quadNode;

On the other hand, the Dungeon example doesn't have an object per map location, just an x and y. It then uses:

void* state = (void*)( y * MAPX + x );

The state can be anything you want, as long as it is unique and you can convert to it and from it.

Now, the methods of Graph.

/**
	Return the least possible cost between 2 states. For example, if your pathfinding 
	is based on distance, this is simply the straight distance between 2 points on the 
	map. If you pathfinding is based on minimum time, it is the minimal travel time 
	between 2 points given the best possible terrain.
*/
virtual float LeastCostEstimate( void* stateStart, void* stateEnd ) = 0;

/** 
	Return the exact cost from the given state to all its neighboring states. This
	may be called multiple times, or cached by the solver. It *must* return the same
	exact values for every call to MicroPather::Solve(). It should generally be a simple,
	fast function with no callbacks into the pather.
*/	
virtual void AdjacentCost( void* state, MP_VECTOR< micropather::StateCost > *adjacent ) = 0;

/**
	This function is only used in DEBUG mode - it dumps output to stdout. Since void* 
	aren't really human readable, normally you print out some concise info (like "(1,2)") 
	without an ending newline.
*/
virtual void  PrintStateInfo( void* state ) = 0;

Call the Solver

MicroPather* pather = new MicroPather( myGraph );	// Although you really should set the default params for your game.

micropather::MPVector< void* > path;
float totalCost = 0;
int result = pather->Solve( startState, endState, &path, &totalCost );

That's it. Given the start state and the end state, the sequence of states from start to end will be written to the vector.

MicroPather does a lot of caching. You want to create one and keep in around. It will cache lots of information about your graph, and get faster as it is called. However, for caching to work, the connections between states and the costs of those connections must stay the same. (Else the cache information will be invalid.) If costs between connections does change, be sure to call Reset().

pather->Reset();

Reset() is a fast call if it doesn't need to do anything.

Future Improvements and Social Coding

I really like getting patches, improvements, and performance enhancements. Some guidelines:

  • Pull requests are the best way to send a change.
  • The "ease of use" goal is important to this project. It can be sped up by deeper integration into the client code (all states must subclass the State object, for example) but that dramatically reduces usability.

Thanks for checking out MicroPather!

Lee Thomason

Comments
  • Micropather with obstacles ?

    Micropather with obstacles ?

    Hello, I tried, like everyone here, to do path finding with Micropather. At the start, it worked well, but when i added obstacles, ...problem. Maybe you'll understand me more with a code ? Here it is: main.cpp: (How do I use the code thing ? Sorry I'm new in github) [code] const int level[] = { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 0, 1, 0, 0, 2, 0, 3, 3, 3, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 3, 3, 3, 0, 0, 0, 1, 1, 1, 2, 0, 0, 0, 0, 1, 0, 3, 0, 2, 2, 0, 0, 1, 1, 1, 1, 2, 0, 2, 0, 1, 0, 3, 0, 2, 2, 2, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 3, 2, 2, 2, 0, 0, 0, 0, 1, 1, 1, 1, };

    const int obslevelIso[] = { //Same size as the prev tab
        0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
    };
    TileMap map;
    if (!map.load("tileset.png", sf::Vector2u(32, 32), level, 16, 8, obslevelIso))
        return -1;
    micropather::MicroPather pather(&map);
    std::vector<void*> path;
    float totalCost;
    
    int result = pather.Solve(map.XYToNode(1, 1), map.XYToNode(3, 3), &path, &totalCost);
    qDebug() << "Result:" << result; //qDebug is same as std::cout
    for (unsigned int i(0); i < path.size(); ++i) {
        int x, y;
        map.NodeToXY(path[i], &x, &y);
        qDebug() << "X, Y:" << x << "," << y;
    }
    

    [/code] And the output is: 1, 1 2, 2 3, 3 But there are obstacles ! (look the obslevelIso tab, the 1 are obstacles) Micropather shouldn't return that... By the way, here's my AdjascentCost func in my Graph: [code] virtual void AdjacentCost( void* node, std::vector< micropather::StateCost > *neighbors ) { int x, y; const int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 }; const int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 }; const float cost[8] = { 1.0f, 1.41f, 1.0f, 1.41f, 1.0f, 1.41f, 1.0f, 1.41f };

        NodeToXY( node, &x, &y );
    
        for( int i=0; i<8; ++i ) {
            int nx = x + dx[i];
            int ny = y + dy[i];
    
            if (passable(XYToNode(nx, ny)) == 0) { //No obstacle
                micropather::StateCost nodeCost = { XYToNode( nx, ny ), cost[i] };
                neighbors->push_back( nodeCost );
            } else { //I tried without the else too, it did the same...
                micropather::StateCost nodeCost = { XYToNode( nx, ny ), FLT_MAX };
                neighbors->push_back( nodeCost );
            }
        }
    }
    

    [/code] So, can you help me please ? Thanks.

  • Diagonal movement through obstacles?

    Diagonal movement through obstacles?

    Hello, I've been playing around with MicroPather and would like to thank you for very nice lightweight "lib" :) It works supreme, just one problem: my path is going diagonally through obstacles. Did I miss something in the API? If not, what is the easiest workaround? I do not want to raise diagonal movement cost if possible. diagonal_movement

  • Add a virtual comperator function to the MicroPather class

    Add a virtual comperator function to the MicroPather class

    I've introduced a virtual comperator method to the MicroPather class. This way comparison of two nodes can be done in the Graph subclass. There might be other places where replacing node A == node B with graph->NodesEqual(A, B) might be necessary.

  • #include <cstring> for memset/memcpy

    #include for memset/memcpy

    micropather.h contains some function implementations which reference memset and memcpy, which are defined in <cstring>. This header is not included, so it is currently up to the library user to include it, whether they need it or not. The header should be included in micropather.h or the function implementations should be moved to micropather.cpp.

  • Revert

    Revert "Replaced FastTime with a portable version."

    Reverts leethomason/MicroPather#8

    Sorry, I like the code change, but it drops the windows resolution to unusable answers. Going to have to use something with better resolution.

  • Don't call raw interrupt routines

    Don't call raw interrupt routines

    In the process of integrating your code into one of our projects, we noticed you were directly calling interrupt 3 on MSVC debug builds. This is dangerous -- just use assert, or allow for the calling application to override the definition of assert outside of your header. Assembler interrupts should be reserved for operating system libraries.

  • Infinite Loop.

    Infinite Loop.

    Getting an infinite loop that occurs in "void PathCache::AddItem( const Item& item )".

    I disabled caching by doing the following.

    m_pather = new micropather::MicroPather(this, 0, 8, false);

    I then get a bad access in micropather::PathNode::Unlink where

        void Unlink() {
            next->prev = prev; // next == nullptr  
            prev->next = next;
            next = prev = 0;
        }
    

    The project I have is in 64-bit and in c++ 11.

  • as3 version

    as3 version

    Hi Lee - I pulled a copy of a functional but not-yet-optimized AS3 version of micropather out of the history of a micropather SourceForge project that popped up in a Google search. I couldn't find a version of it being actively maintained or advertised anywhere.

    Do you have any objections to me throwing up a micropather-as3 repo on GitHub? I'm a fan of the library - I used it a number of years ago in several C++ projects, and really appreciate the clean interface.

  • Rename MicroPather::Reset()

    Rename MicroPather::Reset()

    When using MicroPather in a modern application using std::unique_ptr, the Reset method could easily be confused with the reset method of the smart pointer.

    std::unique_ptr<micropather::MicroPather> pather;
    
    // costs between states changed
    pather->Reset();
    
    // delete the pointer explicitly
    pather.reset();
    

    I therefore suggest to rename the Reset method to StateCostChanged or similar. You should keep Reset and use it as a wrapper for the new method in order to keep backwards compatibility, though.

  • Fix warning for `memset` of non-trivial type

    Fix warning for `memset` of non-trivial type

    Tagging #11

    Fixes GCC warning:

    micropather.cpp: In member function ‘void micropather::MicroPather::GetCacheData(micropather::CacheData*)’:
    micropather.cpp:835:33: warning: ‘void* memset(void*, int, size_t)’ clearing an object of non-trivial type ‘struct micropather::CacheData’; use assignment or value-initialization instead [-Wclass-memaccess]
      memset( data, 0, sizeof(*data) );
                                     ^
    In file included from micropather.cpp:43:
    micropather.h:398:9: note: ‘struct micropather::CacheData’ declared here
      struct CacheData {
             ^~~~~~~~~
    
  • Fix signed/unsigned comparison warnings

    Fix signed/unsigned comparison warnings

    Tagging #11

    Fixes the following GCC warnings:

    micropather.cpp: In member function ‘void micropather::PathCache::AddItem(const micropather::PathCache::Item&)’:
    micropather.cpp:808:14: warning: comparison of integer expressions of different signedness: ‘unsigned int’ and ‘int’ [-Wsign-compare]
       if ( index == allocated )
            ~~~~~~^~~~~~~~~~~~
    micropather.cpp: In member function ‘const micropather::PathCache::Item* micropather::PathCache::Find(void*, void*)’:
    micropather.cpp:827:14: warning: comparison of integer expressions of different signedness: ‘unsigned int’ and ‘int’ [-Wsign-compare]
       if ( index == allocated )
            ~~~~~~^~~~~~~~~~~~
    
  • Reusing graph while blocking previously found paths

    Reusing graph while blocking previously found paths

    I'm planning on trying MicroPather out as part of a circuit board autorouter. On a PCB, a given area can only be used by a single trace. So I would like to be able to use a single graph that represents the PCB, and run MicroPather multiple times on it, once for each required trace. Each time a trace is found, I would then need to remove the nodes used by that trace from the graph.

    For performance, I would like to avoid having a second representation of the PCB where I keep track of which areas have been used in previous traces, since, I think, that would require me to generate a new graph and nodes for each trace.

    Can MicroPather be used in this way?

    I've done some successful experiments with MicroPather for my stripboard autorouter, so I'll probably try it first, even if I do have to regenerate the graph from a separate representation for each trace.

  • TinyXml2 Version 5.0.1 minor change request for functions GetErrorStr1 & GetErrorStr2

    TinyXml2 Version 5.0.1 minor change request for functions GetErrorStr1 & GetErrorStr2

    The functions GetErrorStr1 and GetErrorStr2 call GetStr() on a member variable that is a StrPair. If this member variable last operation had been a reset (which is the case most of the time) then call GetStr() will cause the code to throw an assertion. This throw will cause most applications to crash since there is no code to catch that exception. I would suggest the follow changes to those two routines:

    const char* XMLDocument::GetErrorStr1() const { if (_errorStr1.Empty()) { return NULL; }

    return _errorStr1.GetStr();
    

    }

    const char* XMLDocument::GetErrorStr2() const { if (_errorStr2.Empty()) { return NULL; }

    return _errorStr2.GetStr();
    

    }

    This is a simple addition of an "if statement" to check to see if the StrPair is empty and if so return a NULL;

    Thanks Larry

  • Question about usage with moving entities

    Question about usage with moving entities

    My question involves using this pathfinder with other entities moving around on a map.

    My initial thought was to find the best path while ignoring the other moving entities, and then avoid or pathfind (with another MicroPather that is reset every call) around the entities if they block the path. This way I don't need to constantly reset the MicroPather state.

    Is this the right way to go about solving this problem, or am I missing a better solution?

C library designed for the TI MSP432P401R microprocessor and the TI Educational Booster Pack, to easily play and control songs with the integrated Piezo Buzzer.

MusicLib C library designed for the TI MSP432P401R microprocessor and the TI Educational Booster Pack, to easily play and control songs with the integ

Nov 24, 2021
Repository for the App Dev Bootcamp conducted in Spring 2022 for IECSE. Bootcamp mainly focuses on Flutter and Dart.

IECSE-AppDev-Spring-2022 Welcome to IECSE's App Dev Bootcamp, Spring'22. Ever wondered how applications like Instagram, WhatsApp, and others are built

Jul 18, 2022
The Gecko SDK (GSDK) combines all Silicon Labs 32-bit IoT product software development kits (SDKs) based on Gecko Platform into a single, integrated SDK.

Silicon Labs Gecko SDK (GSDK) The Gecko SDK (GSDK) combines Silicon Labs wireless software development kits (SDKs) and Gecko Platform into a single, i

Nov 24, 2022
A generic post-processing injector for games and video software.

ReShade This is a generic post-processing injector for games and video software. It exposes an automated way to access both frame color and depth info

Dec 4, 2022
This repo does not contain any skins that work by themselves, but rather addons to already existing skins like CakeOS and Polybar
This repo does not contain any skins that work by themselves, but rather addons to already existing skins like CakeOS and Polybar

Rainmeter-addons ⚠ This repo does not contain any skins that work by themselves, but rather addons to already existing skins like CakeOS and Polybar E

Nov 3, 2022
This is kdmapper but it doesn't use ExAllocatePool instead it allocates pages to avoid being in BigPoolTable,

KDMapper without allocating memory in BigPoolTable Original creator https://github.com/z175 Improved by https://github.com/TheCruZ TheCruz has intergr

Nov 22, 2022
Inject .NET assemblies into an existing process
Inject .NET assemblies into an existing process

inject-assembly - Execute .NET in an Existing Process This tool is an alternative to traditional fork and run execution for Cobalt Strike. The loader

Nov 28, 2022
An interpreter for finding subtle bugs in programs written in standard C

tis-interpreter This is tis-interpreter, an interpreter of C for detecting undefined behavior. tis-interpreter detects subtle bugs in C programs that

Dec 3, 2022
Create Hacktoberfest PRs. Star this Repo!⭐
Create Hacktoberfest PRs. Star this Repo!⭐

Hacktoberfest 2021 Link To HacktoberFest 2021 Event details : Hacktoberfest is a month-long challenge. It happens every year in the month of October.

Oct 6, 2022
Raise Genuine PRs only. Your PRs will be accepted, keep patience. Star This Repo. You aren't allowed to Update README.md

Welcome To Hacktoberfest 2021 Link To HacktoberFest 2021 Event details : Hacktoberfest® is open to everyone in our global community. Whether you’re a

Sep 16, 2022
Raise Genuine PRs only. Your PRs will be accepted, keep patience. Star This Repo. You aren't allowed to Update README.md

Hacktoberfest 2021 Link To HacktoberFest 2021 Event details : Hacktoberfest® is open to everyone in our global community. Whether you’re a developer,

Dec 24, 2021
SDR++ is a cross-platform and open source SDR software with the aim of being bloat free and simple to use.
SDR++ is a cross-platform and open source SDR software with the aim of being bloat free and simple to use.

SDR++ is a cross-platform and open source SDR software with the aim of being bloat free and simple to use.

Dec 5, 2022
ASMotor is a portable and generic assembler engine and development system written in ANSI C99

ASMotor is a portable and generic assembler engine and development system written in ANSI C99 and licensed under the GNU Public License v3. The package consists of the assembler, the librarian and the linker. It can be used as either a cross or native development system.

Nov 18, 2022
Defold Engine integration with Yandex.Metrica to track your games on Yandex.Games.
Defold Engine integration with Yandex.Metrica to track your games on Yandex.Games.

Yandex.Metrica for Defold Yandex.Metrica is a free of charge web analytics tool for websites, that's the reason why we can use it for HTML5 games. Yan

Nov 26, 2022
An embedded CAN bus sniffer which is able to monitor any of the vehicle internal CAN bus and perform some action by triggering new CAN messages.
An embedded CAN bus sniffer which is able to monitor any of the vehicle internal CAN bus and perform some action by triggering new CAN messages.

An embedded CAN bus sniffer which is able to monitor any of the vehicle internal CAN bus and perform some action by triggering new CAN messages. In this way certain vehicle functionality can be triggered by responding to custom steering wheel button events, or use the vehicle virtual cockpit to display OBD-PIDs values instead of relying on an external display to present new information to the user

Nov 28, 2022
GraphicsFuzz provides tools for automatically finding and simplifying bugs in graphics drivers, specifically graphics shader compilers.

GraphicsFuzz GraphicsFuzz is a set of tools for testing shader compilers GraphicsFuzz provides tools for automatically finding and simplifying bugs in

Nov 29, 2022
HESS HAMILTONIAN PATH COMPLETE (2021) black-box for Hamiltonian Path Problem

The original HESS (Hyper Exponential Space Sorting) is a polynomial black-box optimization algorithm, that work very well with any NP-Complete, or NP-Hard problem

Jan 19, 2022
"Sigma File Manager" is a free, open-source, quickly evolving, modern file manager (explorer / finder) app for Windows, MacOS, and Linux.

"Sigma File Manager" is a free, open-source, quickly evolving, modern file manager (explorer / finder) app for Windows, MacOS, and Linux.

Dec 1, 2022