miNav Tutorial
Introduction
This tutorial is aimed at teaching how to use the miNav library to perform AI Pathfinding. If you don't have a copy of the miNav library then you can find on here. This tutorial will show how to compile, link to, start-up, use and close the miNav library. This tutorial has been written for miNav Version 0.1.
miNav is a preprocessed Map and Node based pathfinding library. Which means you must work with Nodes that represent regions of your map and link them accordingly. Whether or not a location in your map is in the region of a Node is left up you to make your program to determine. The basic idea of this library is that you create a Map, add Nodes and then solve all the possible pathfinding queries in advance and store them, then use them later on. THIS IS NOT A REALTIME AI PATHFINDING LIBRARY, pathfinding is meant to be calculated once, after that you are simply recalling the stored solutions.
This library is still only in version 0.1. It works in my tests, but I made it so I know exactly how to use it, so it might not work for you if you use it slightly differently to me. If you discover any bugs or are getting unexpected errors trying to do something with this library, just email me at mindinsomnia@gmail.com
This library was released under the MIT licence, so you can do pretty much anything with it, so if you like it and can get it working for you, then feel free to use it for anything you want. The only think you can't do is claim you made it, other than that, have fun!
Compiling
To compile just setup your compiler to compile a static library, this is done differently for each type of compiler, so it is not shown how to do it here. Compile the miNav.h file and the miNav.cpp file. Save the object (.o) file created. There's not a lot which I can say here to help you here without writing a tutorial on compiling things in tonnes of different compilers... which I don't want to do and is not the focus of this tutorial. Maybe someday I'll write a special tutorial for but for now if you don't know how to work your compiler then go to a programming forum and ask around for help.
You don't really need to compile the library because it comes with the compiled object file and header to use, you really just need to link to them. I just thought I'd mention something about compiling in case someone decided they wanted to modify the library and recompile it.
Linking
To link to the compiled library just include the miNav.h header file and link to the object file (.o) miNav.o. All functions and classes in the miNav library are under the namespace "miNav", so you must use that namespace.
Example
#include "miNav.h"
using namespace miNav;
Starting Up
To start the miNav library you must create a miNavDevice. This device is the object that will hold everything you do in the library, so make sure you keep track of the pointer to it, it's important because you won't be able to do anything without that pointer... not even delete the Device (aka a memory leak). The pointer returned is of type 'miNavDevice'.
Example
miNavDevice* myDevice = new miNavDevice;
Adding Maps to the miNavDevice
To add a map to the miNavDevice you use your devices addMap function. The function returns a pointer to the map of type 'Map'.
Example
Map* myMap = myDevice->addMap();
Adding Nodes to the Maps
To add a Node to a Map use the addNode function. You must supply in the parameters 3 floating point numbers ('float') which represent the X,Y,Z coordinates. The function returns a pointer to the created Node. Remember you must keep track of all these pointers, you can do so just be having lots of different pointers like this, which is nice and simple or by having an array of pointers. Or maybe if you wish to go more advanced you could use a 'linked list'. Whatever you do, just make sure you don't lose them, cause there is no way of getting them back once they're created.
Example
Node* myNode = myMap->addNode(-2,0.0098,87658.233);
Linking Nodes
The Nodes when added represent points on the map, but none of those points are connected yet. To connect nodes you must use the connect() or connect2way() function. Both require 2 parameters which are both pointers to Nodes. The connect() function will connect the first node to the second node, BUT NOT THE SECOND NODE TO THE FIRST. It is a one way connection. To make the connection 2 way you use the connect2way function.
Example
myMap->connect(FireEscape_Upstairs,FireEscape_Downstairs);
myMap->connect2way(Kitchen,LoungeRoom);
Solving the Map
The miNav library is designed to pre-calculate all pathfinding in advance, not in realtime. So you must startup the library, create the maps, then add nodes, then link them and once your done doing that, you must 'solve' the Map. When you solve the map all the possible pathfinding queries are done in advance and stored for future use. To solve a map is very simple:
Example
myMap->solve();
Using Solutions
To query the solutions created, you use the getSolution() function. You must specify two Nodes in the parameters of the function. The first parameter is the current position, the second is the destination. The function returns a pointer to the first node you must travel to, to reach the destination. A simple loop of updating the current position to the returned solution would eventually reach the destination node.
Example
Node* NextStep = myMap->getSolution(CurrentPosition, GoalDestination);
Example
Node* Position;
Node* Destination;
Destination = Node7;
Position = Node15;
while(Position != Destination)
{
Position = myMap->getSolution(Position, Destination);
}
Where is that solution?
You can get the position of that solution by using the Node's X, Y and Z values.
Example
float TargetX;
float TargetY;
float TargetZ;
Node* NextStep = myMap->getSolution(CurrentPosition, GoalDestination);
TargetX = NextStep->X;
TargetY = NextStep->Y;
TargetZ = NextStep->Z;
Close the miNav Library
All Maps and Nodes created in miNav can be deleted by deleting the parent Device. Deleting the Device will create a chain reaction deleting all the Maps added to it, deleting the Maps creates a similar chain reaction deleting all the Nodes added to it. It's recommended to create just one device and add all your maps to it. Making closing the library later on as simple as one line of code:
Example
delete myDevice; // Deletes everything created in the Device
Just make sure that you do actually do this, otherwise your program will have a memory leak as memory will be being allocated but not released when finished being used.
Other Functions?
There are other functions, but they're mostly just functions to delete Nodes or Maps individually or disconnect connected Nodes. You can find most of these functions just by looking at the miNav.h file.
Warnings
This library is suited for doing LOTS of pathfinding on small maps (0-40 nodes) really quickly (like instantly!). I wouldn't recommend using it for larger maps as the size of the memory the library will use for storing solutions will increase exponentially. Although for large scale areas to pathfinded it might be worth considering to use multiple maps of different sizes and join them up.
For example:
If you were making a GTA style game with a huge game map with lots of cities, you could create one map which has nodes at each city. Then you could make more maps, one for each city, where the nodes represent the roads and intersections. This reduces the memory used massively but will require you to code a method of determining when to use which maps and which nodes are apart of those maps.
I haven't done much experimenting with this library yet, so I don't know what will happen if a mistake is made using it. I for instance don't know what will happen if you try to connect 2 nodes that exist in different maps. If you do this yourself, I'd love to hear what the results are. :D
Example Program
Code
#include <iostream>
#include "miNav.h"
using namespace std;
using namespace miNav;
int main()
{
// Create a miNav Device
miNavDevice* myDevice = new miNavDevice;
// Add a map to Device
Map* myMap = myDevice->addMap();
// Make Nodes
Node* N1 = myMap->addNode(0,0,0);
Node* N2 = myMap->addNode(10,0,0);
Node* N3 = myMap->addNode(5,12,0);
Node* N4 = myMap->addNode(0,10,0);
Node* N5 = myMap->addNode(20,10,0);
// Connect the nodes
myMap->connect2way(N1,N4);
myMap->connect2way(N1,N2);
myMap->connect2way(N2,N3);
myMap->connect2way(N4,N3);
myMap->connect(N3,N5);
myMap->connect(N5,N2);
// Solve the map
myMap->solve();
// Display the memory addresses of the nodes
cout << "N1 - " << N1 << endl;
cout << "N2 - " << N2 << endl;
cout << "N3 - " << N3 << endl;
cout << "N4 - " << N4 << endl;
cout << "N5 - " << N5 << endl;
// Using a 'Node' pointer can simplify tests like position!=goal. This short code
// snippet starts at node “N1” and travels to “N3” using the solutions.
Node* position = N1;
Node* goal = N3;
while(position!=goal)
{
// Display the current position and the goal
cout << "Position:" << position << " Goal:" << goal << endl;
// Move to the solution
position = myMap->getSolution(position,goal);
}
// Reaching this line means position must equal goal
// therefore no errors and successful pathfinding
cout << "Success\n";
system("PAUSE");
// Delete all created data
delete myDevice;
cout << "Device deleted\n";
system("PAUSE");
// Close
return 0;
}
Output:
N1 - 0x33e08
N2 - 0x33e38
N3 - 0x33e68
N4 - 0x33e98
N5 - 0x33ec8
Position:0x33e08 Goal:0x33e68
Position:0x33e98 Goal:0x33e68
Success
Press any key to continue . . .
Device deleted
Press any key to continue . . .
