gm_navigation - All in one navigation solution

gm_navigation makes navigation tasks a breeze.
This all in one navigation module lets you easily create a node table that you can use for finding paths using a A* path finding algorithm.
All the other navigation modules currently available were too laggy for my needs. I have profiled this code and found it far more superior than the lua versions.


Functions

[lua]
nav.CreateNav((number)gridsize) – Returns a new Nav with a set grid size

Nav:GetNodeByID(number) – Returns the node with the given ID
Nav:GetNodes() – Returns a table with all the nodes
Nav:GetNodeTotal() – Returns the number of total nodes
Nav:StartGeneration() – Start generating nodes, used to setup variables
Nav:AddGroundSeed(Pos, Normal) – Adds a walkable seed. During navigation the node will start spreading out from the first walkable seed. Once that seed is used up it will go on to the second, third and so on. The module will account for seed overlapping.
Nav:AddAirSeed(Pos) – Adds a seed for air nav generation (Similar to AirGroundSeed, but it will make air nodes).
Nav:ClearGroundSeeds() – Simply removes all ground seeds
Nav:ClearAirSeeds() – Simply removes all ground seeds
Nav:SetupMaxDistance(position, (number)distance) – Confines all the generated nodes to a set vector within the specified distance
Nav:Generate(function(Nav) print(“Finished Generating”) end [[, function(Nav, GeneratedNodeCount) print(“Generating”, Nav, “Nodes Generated:”, GeneratedNodeCount) end]] ) – Generates the node graph (threaded), will call the first callback function once it finishes. The optional second argument will be called while the nav is being generated every second. This function returns true if it was successfully added to the thread queue.
Nav:FullGeneration() – Generates the node graph (Non threaded), returns the amount of seconds it took to generate.
Nav:IsGenerated() – Returns a bool based on if its generated or not
Nav:FindPath(function(Nav, FoundPath, Path) end) – Finds a path from the start to the end node (Specified from Nav:SetStart / End). The callback function is passed the nav it was called on, boolean FoundPath (true a path was found), and a path table that contains a series of nodes the path took from start to end. The optional second argument will be called while the nav is being generated every second. This function returns true if it was successfully added to the thread queue.
Nav:FindPathHull(mins, maxs, function(Nav, FoundPath, Path) end) – Similar to FindPath but this will trace the specified hull along the path to ensure there is room for something with the hull size to move along it. It’s useful if you are moving an entity along a path that might have entities / the level blocking it. Mins, and maxs are vectors for the hull size. This function returns true if it was successfully added to the thread queue.
Nav:GetHeuristic() – Returns an heuristic enumeration
Nav:GetStart() – Returns the starting node
Nav:GetEnd() – Returns the ending node
Nav:SetHeuristic(HEURISTIC_BLAH) – Put one of those fun heuristic enum’s here
Nav:SetStart(Node) – Set the start node for FindPath
Nav:SetEnd(Node) – Set the endnode for FindPath
Nav:GetNode(position) – Returns the node at the position (Can be off by GridSize * 0.45)
Nav:GetClosestNode(position) – Returns the closest node to said position
Nav:GetNodesInSphere(pos, radius) – Returns a table of nodes found within the radius of the pos
Nav:GetDiagonal() – Returns a boolean for diagonal linking
Nav:SetDiagonal(bool) – Used to enable / disable diagonal linking
Nav:GetGridSize() – Returns grid size (number)
Nav:SetGridSize(number) – Set the grid size (Space between the nodes)
Nav:GetMask() – Returns the trace mask used during the node generation
Nav:SetMask(MASK_*) – Set the trace mask
Nav:CreateNode(Pos, Normal) – Returns a new node at position Pos and normal Normal
Nav:RemoveNode(node) – Removes node from existence

Nav:Save(filename) – Saves the Nav to a file
Nav:Load(filename) – Load the Nav from a file

Node:GetID() – Returns the id of the node in the GetNodes table. Useful for comparing nodes
Node:GetPosition() – Returns vector of the nodes position
Node:GetPos() – Alias of Node:GetPosition()
Node:GetNormal() – Returns vector of the nodes normal
Node:GetConnections() – Returns node table of the nodes connections
Node:IsConnected(OtherNode) – Returns a bool if Node is connected to OtherNode
Node:SetPosition(Pos) – Change the nodes position
Node:SetNormal(Normal) – Change the nodes normal
Node:ConnectTo(Node2, Dir) – Link Node to Node2 in direction Dir
Node:RemoveConnection(Dir) – Removes connection in the direction Dir
[/lua]


Enumerations

[lua]
nav.NORTH
nav.SOUTH
nav.EAST
nav.WEST
nav.NORTHEAST
nav.NORTHWEST
nav.SOUTHEAST
nav.SOUTHWEST
nav.UP
nav.DOWN
nav.LEFT
nav.RIGHT
nav.FORWARD
nav.BACKWARD
nav.NUM_DIRECTIONS
nav.NUM_DIRECTIONS_DIAGONAL
nav.NUM_DIRECTIONS_MAX
nav.HEURISTIC_MANHATTAN
nav.HEURISTIC_EUCLIDEAN
[/lua]

Example File
Example file should be used clientside so you can see what your doing.
Put it in your autorun directory and type “snav_generate_ground” to generate some ground nodes.
snav_generate_air to generate air nodes
snav_generate_ground_air to generate ground and air nodes.
Hold alt to view the nodes.
Go near a node and type “snav_setstart”
Go near another node and type “snav_setend”
Hold shift to view the path.


Download

Source: http://spacetechmodules.googlecode.com/svn/trunk/gm_navigation
Windows:

Client: http://spacetechmodules.googlecode.com/svn/trunk/gm_navigation/Release%20-%20Client/gmcl_navigation_win32.dll
Server: http://spacetechmodules.googlecode.com/svn/trunk/gm_navigation/Release%20-%20Server/gmsv_navigation_win32.dll

The example file will make a fun picture like this

http://content.screencast.com/users/Spacetech/folders/Jing/media/8a37db61-2749-4abd-866b-15b8dac53a1b/2010-06-14_2005.png

gm_construct with 64 grid size, generated in 15 seconds with diagonal linking enabled. Node Total: 8092, Link Total: 58746 (Sorry for horrible quality)

http://img706.imageshack.us/img706/739/201006201634.png

Demonstration of Nav:FindPathHull with a hull about the size of a player.

Ground and air nodes:

Wicked! with this and gm_aigraph we can finally have efficient, intelligent bots.

[img_thumb]http://img229.imageshack.us/img229/3985/gmconstruct0044.jpg[/img_thumb]

Works amazingly. I am definitely going to use this for an RTS I’m working on.

Does it also work for non-noded maps?

You shouldn’t need to use gm_aigraph, this module can make better nodes.

In the example file if you comment out this line and run it on gm_construct it can fully navigate the map in 5 seconds
[lua]
Nav:SetupMaxDistance(ply:GetPos(), 256) – All nodes must stay within 1024 from the players position
[/lua]

That is just debug stuff from the console, you can see that it created 2867 nodes and the total link count between the node are 10654 (Links are used for A* pathfinding)

Kind of a bad quality picture but if you remove this check then you can see all the nodes at once (It might lag depending on your pc)
[lua]
if(PlyPos:Distance(v:GetPosition()) <= 512) then
[/lua]

http://img94.imageshack.us/img94/8831/201006151019.jpg

Does it generate a graph for the entire map ( it looks like it the screenshot, so I am unclear )?

If so, FUCK YES. I have been wanting something like this for a long time.

Does this save and load the grid in the navmesh format for maps ( .nav )? If so, is it compatible with CSS navmeshes?

If so, you are a hero.

That screenshot has it generated for the whole map.
You can make it generate for the whole map or just small parts of the map.

This is not compatible with CSS navmeshs, but this does feature saving and loading. You can generate as many nodes as you want and then save it to a file so you can load it on map change. In the example file it saves the map and then loads it right after and prints debug stuff for both so you can see that they are the exact same thing.

This doesn’t make a real nav mesh, just a bunch of nodes that are linked together for A* path finding. It still allows for advanced AI movement (Checkout Darkland RPG stuff)

I wrote a saving to AI nav file function. But I scrapped it because Valve has a stupidly small limit of 1500 nodes.

I guess L4D/2 has a larger node limit. Or more fluid movement between nodes.

Since the AI code is purely in the SDK, perhaps we should ask Garry to up the node limit to 3000 or more. Or better yet, make it dynamic.

Thank you. This is a life saver.

If you have a max sized map with a lot of train track tunnels in side then you need more then 4500.

Regardless, we need it to be dynamic. I think this limit is purely performance safe guards from HL2.

Help… Whenever I try to use the example. It crashes and gives me a “Lua Error Dump!” message. Can anyone explain this? Suggest any possible solutions?

I had this problem as well, but run it once on the client, enter “snav” in the console and then hold the alt key.

This is awesome. People will finally be able to create in-depth gamemodes that involve things that navigate independantly.

I’ve been using vector clouds(just a map of nodes without the links) for internal and external floor surfaces for about half a year now for my weather system/door system/npc director.

I’m still finding uses for it.

Are you trying it serverside or clientside? Do you have any crash dumps you can send me?

I think you’re supposed to free the references you use in the shutdown function. (ILuaInterface::FreeReference)

Correct me if I’m wrong.

Oh yes, you need to free references.

Oh.

My.

God.

I assumed when the shutdown function was called the lua state was destroyed, I guess I was wrong.
I updated my modules.
Thanks