• gm_navigation - All in one navigation solution
    254 replies, posted
  • Avatar of Spacetech
  • 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. [highlight]Functions[/highlight] [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] [highlight]Enumerations[/highlight] [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] [url=https://spacetechmodules.googlecode.com/svn/trunk/examples/cl_navigation.lua]Example File[/url] 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. [highlight]Download[/highlight] Source: [url]http://spacetechmodules.googlecode.com/svn/trunk/gm_navigation[/url] Windows: Client: [url]http://spacetechmodules.googlecode.com/svn/trunk/gm_navigation/Release%20-%20Client/gmcl_navigation_win32.dll[/url] Server: [url]http://spacetechmodules.googlecode.com/svn/trunk/gm_navigation/Release%20-%20Server/gmsv_navigation_win32.dll[/url] The example file will make a fun picture like this [img]http://content.screencast.com/users/Spacetech/folders/Jing/media/8a37db61-2749-4abd-866b-15b8dac53a1b/2010-06-14_2005.png[/img] gm_construct with 64 grid size, generated in 15 seconds with diagonal linking enabled. Node Total: 8092, Link Total: 58746 (Sorry for horrible quality) [img]http://img706.imageshack.us/img706/739/201006201634.png[/img] Demonstration of Nav:FindPathHull with a hull about the size of a player. [img]http://i.imgur.com/mMEou.jpg[/img] Ground and air nodes: [img]http://i.imgur.com/M95Zf.jpg[/img]
  • Avatar of blackops7799
  • [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.
  • Avatar of Grocel
  • [QUOTE=blackops7799;22624954][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.[/QUOTE] Does it also work for non-noded maps?
  • Avatar of Spacetech
  • [QUOTE=Mr_Roberto;22623637]Wicked! with this and gm_aigraph we can finally have efficient, intelligent bots.[/QUOTE] [QUOTE=Grocel;22629956]Does it also work for non-noded maps?[/QUOTE] 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] [quote=CONSOLE] Node Total 2867 Link Total 10654 GetNode -1472.0000 704.0000 -148.0303 -1472.0000 704.0000 -148.0303 GetClosestNode Node: 28B183B8 Node Info table: 2B1FC870 2867 2867 First Node 768.0000 -95.0000 -143.9688 768.0000 -95.0000 -143.9688 Last Node -1984.0000 -2240.0000 -159.9688 -1984.0000 -2240.0000 -159.9688 GetNodeTotal 1 2867 GetNodeTotal 2 2867 Start 768.0000 -95.0000 -143.9688 End -1984.0000 -2240.0000 -159.9688 Save true Load true Node Total 2867 Link Total 10654 GetNode 1216.0000 2240.0000 -31.9688 1216.0000 2240.0000 -31.9688 GetClosestNode Node: 2B284190 Node Info table: 290FDC58 2867 2867 First Node 768.0000 -95.0000 -143.9688 768.0000 -95.0000 -143.9688 Last Node -1984.0000 -2240.0000 -159.9688 -1984.0000 -2240.0000 -159.9688 GetNodeTotal 1 2867 GetNodeTotal 2 2867 Start 768.0000 -95.0000 -143.9688 End -1984.0000 -2240.0000 -159.9688 Save true [/quote] 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] [img]http://img94.imageshack.us/img94/8831/201006151019.jpg[/img]
  • Avatar of Kogitsune
  • 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.
  • Avatar of Spacetech
  • [QUOTE=Kogitsune;22633094]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.[/QUOTE] 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)
  • Avatar of haza55
  • 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.
  • Avatar of Grocel
  • [QUOTE=haza55;22650357]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.[/QUOTE] If you have a max sized map with a lot of train track tunnels in side then you need more then 4500.
  • Avatar of haza55
  • [QUOTE=Grocel;22655988]If you have a max sized map with a lot of train track tunnels in side then you need more then 4500.[/QUOTE] Regardless, we need it to be dynamic. I think this limit is purely performance safe guards from HL2.
  • Avatar of Eidolon
  • 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?
  • Avatar of Grocel
  • I had this problem as well, but run it once on the client, enter "snav" in the console and then hold the alt key.
  • Avatar of robowurmz
  • This is awesome. People will finally be able to create in-depth gamemodes that involve things that navigate independantly.
  • Avatar of haza55
  • 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.
  • Avatar of Spacetech
  • [QUOTE=Eidolon;22656652]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?[/QUOTE] Are you trying it serverside or clientside? Do you have any crash dumps you can send me?
  • Avatar of Skondra
  • I think you're supposed to free the references you use in the shutdown function. (ILuaInterface::FreeReference) Correct me if I'm wrong.
  • Avatar of haza55
  • [QUOTE=Skondra;22659055]I think you're supposed to free the references you use in the shutdown function. (ILuaInterface::FreeReference) Correct me if I'm wrong.[/QUOTE] Oh yes, you need to free references.
  • Avatar of Spacetech
  • [QUOTE=Skondra;22659055]I think you're supposed to free the references you use in the shutdown function. (ILuaInterface::FreeReference) Correct me if I'm wrong.[/QUOTE] I assumed when the shutdown function was called the lua state was destroyed, I guess I was wrong. I updated my modules. Thanks
  • Avatar of Skondra
  • [QUOTE=bobthe2lol;22729117]Im confused by the video. Are you doing that or is lua?[/QUOTE] If it's him then he needs to turn down his mouse sensitivity.
  • Avatar of Spacetech
  • [QUOTE=Grocel;22729698]Can you add diagonal linking?[/QUOTE] There is diagonal linking if you compile with #define DIAGONAL I'm going to see if I can make it so you can just Nav:SetDiagonal(bool)
  • Avatar of deluvas
  • Is there any chance you can add some functions to customize the way the nodes are generated? For example: I would like the generator not to ignore player clip. Is that possible?
  • Avatar of Spacetech
  • [QUOTE=Grocel;22729698]Can you add diagonal linking?[/QUOTE] [QUOTE=deluvas;22755247]Is there any chance you can add some functions to customize the way the nodes are generated? For example: I would like the generator not to ignore player clip. Is that possible?[/QUOTE] I just updated the module. I fixed various crashes and added the following functions (along with some new enumerations for diagonal linking) [lua] Nav:GetDiagonal() Nav:SetDiagonal(bool) Nav:GetGridSize() Nav:SetGridSize(number) Nav:GetMask() Nav:SetMask(MASK_*) [/lua] Revisit the first post for function descriptions and some new images. The example file has also been updated.