1. Post #1
    Gold Member
    Spacetech's Avatar
    January 2006
    510 Posts
    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
    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
    

    Enumerations
    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
    

    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.c.../gm_navigation
    Windows:

    Client: http://spacetechmodules.googlecode.c...tion_win32.dll
    Server: http://spacetechmodules.googlecode.c...tion_win32.dll

    The example file will make a fun picture like this


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


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


    Ground and air nodes:
    Reply With Quote Edit / Delete Reply United States Show Events Lua King x 24Useful x 11Winner x 4Dumb x 2Optimistic x 2Funny x 1Friendly x 1 (list)

  2. Post #2
    Mr_Roberto's Avatar
    October 2008
    133 Posts
    Wicked! with this and gm_aigraph we can finally have efficient, intelligent bots.
    Reply With Quote Edit / Delete Reply United States Show Events Agree Agree x 4Optimistic Optimistic x 1 (list)

  3. Post #3
    Gold Member
    blackops7799's Avatar
    December 2006
    1,714 Posts


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

  4. Post #4
    Grocel's Avatar
    October 2008
    1,233 Posts


    Works amazingly. I am definitely going to use this for an RTS I'm working on.
    Does it also work for non-noded maps?

  5. Post #5
    Gold Member
    Spacetech's Avatar
    January 2006
    510 Posts
    Wicked! with this and gm_aigraph we can finally have efficient, intelligent bots.
    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
    Nav:SetupMaxDistance(ply:GetPos(), 256) -- All nodes must stay within 1024 from the players position
    

    CONSOLE posted:

    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
    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)
    if(PlyPos:Distance(v:GetPosition()) <= 512) then
    

    Reply With Quote Edit / Delete Reply United States Show Events Lua King Lua King x 7Winner Winner x 1 (list)

  6. Post #6
    Gold Member
    Kogitsune's Avatar
    September 2005
    2,818 Posts
    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.

  7. Post #7
    Gold Member
    Spacetech's Avatar
    January 2006
    510 Posts
    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)
    Reply With Quote Edit / Delete Reply United States Show Events Lua King Lua King x 1 (list)

  8. Post #8
    Box collector
    haza55's Avatar
    October 2005
    545 Posts
    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.
    Reply With Quote Edit / Delete Reply Australia Show Events Friendly Friendly x 1 (list)

  9. Post #9
    Terabit's Avatar
    December 2009
    217 Posts
    Thank you. This is a life saver.

  10. Post #10
    Grocel's Avatar
    October 2008
    1,233 Posts
    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.
    If you have a max sized map with a lot of train track tunnels in side then you need more then 4500.
    Reply With Quote Edit / Delete Reply Germany Show Events Disagree Disagree x 1 (list)

  11. Post #11
    Box collector
    haza55's Avatar
    October 2005
    545 Posts
    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.

  12. Post #12
    Eidolon's Avatar
    April 2008
    114 Posts
    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?

  13. Post #13
    Grocel's Avatar
    October 2008
    1,233 Posts
    I had this problem as well, but run it once on the client, enter "snav" in the console and then hold the alt key.

  14. Post #14
    Gold Member
    robowurmz's Avatar
    April 2007
    2,245 Posts
    This is awesome. People will finally be able to create in-depth gamemodes that involve things that navigate independantly.

  15. Post #15
    Box collector
    haza55's Avatar
    October 2005
    545 Posts
    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.

  16. Post #16
    Gold Member
    Spacetech's Avatar
    January 2006
    510 Posts
    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?
    Are you trying it serverside or clientside? Do you have any crash dumps you can send me?
    Reply With Quote Edit / Delete Reply United States Show Events Lua King Lua King x 1 (list)

  17. Post #17
    Skondra's Avatar
    June 2009
    333 Posts
    I think you're supposed to free the references you use in the shutdown function. (ILuaInterface::FreeReference)

    Correct me if I'm wrong.

  18. Post #18
    Box collector
    haza55's Avatar
    October 2005
    545 Posts
    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.

  19. Post #19
    diaoyudao shi ZHONGGUO de
    Disseminate's Avatar
    December 2007
    4,055 Posts
    Oh.

    My.

    God.
    Reply With Quote Edit / Delete Reply Canada Show Events Agree Agree x 13Dumb Dumb x 1 (list)

  20. Post #20
    Gold Member
    Spacetech's Avatar
    January 2006
    510 Posts
    I think you're supposed to free the references you use in the shutdown function. (ILuaInterface::FreeReference)

    Correct me if I'm wrong.
    I assumed when the shutdown function was called the lua state was destroyed, I guess I was wrong.
    I updated my modules.
    Thanks
    Reply With Quote Edit / Delete Reply United States Show Events Lua King Lua King x 1 (list)

  21. Post #21
    tomato3017's Avatar
    April 2007
    116 Posts
    Wow, someone has been busy in Visual Studio.
    Reply With Quote Edit / Delete Reply United States Show Events Agree Agree x 1 (list)

  22. Post #22
    Gold Member
    maurits150's Avatar
    February 2007
    1,816 Posts
    This module is genius.

    Reply With Quote Edit / Delete Reply Netherlands Show Events Agree Agree x 5Useful Useful x 1Informative Informative x 1Winner Winner x 1 (list)

  23. Post #23
    Gold Member

    April 2009
    726 Posts
    Cool, gave me a idea :D
    Reply With Quote Edit / Delete Reply Denmark Show Events Agree Agree x 1 (list)

  24. Post #24
    Gold Member
    bobthe2lol's Avatar
    July 2007
    1,370 Posts
    Im confused by the video. Are you doing that or is lua?
    Reply With Quote Edit / Delete Reply United States Show Events Dumb Dumb x 7 (list)

  25. Post #25
    Skondra's Avatar
    June 2009
    333 Posts
    Im confused by the video. Are you doing that or is lua?
    If it's him then he needs to turn down his mouse sensitivity.
    Reply With Quote Edit / Delete Reply United Kingdom Show Events Funny Funny x 41Agree Agree x 1 (list)

  26. Post #26
    Pass along
    commander204's Avatar
    May 2008
    4,065 Posts
    I think it navigates him there, that is why it is so choppy.
    Reply With Quote Edit / Delete Reply France Show Events Dumb Dumb x 1 (list)

  27. Post #27
    Grocel's Avatar
    October 2008
    1,233 Posts
    Can you add diagonal linking?

  28. Post #28
    Gold Member
    Spacetech's Avatar
    January 2006
    510 Posts
    Can you add diagonal linking?
    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)
    Reply With Quote Edit / Delete Reply United States Show Events Lua King Lua King x 2 (list)

  29. Post #29
    deluvas's Avatar
    September 2006
    85 Posts
    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?

  30. Post #30
    Gold Member
    Spacetech's Avatar
    January 2006
    510 Posts
    Can you add diagonal linking?
    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?
    I just updated the module.
    I fixed various crashes and added the following functions (along with some new enumerations for diagonal linking)

    Nav:GetDiagonal()
    Nav:SetDiagonal(bool)
    Nav:GetGridSize()
    Nav:SetGridSize(number)
    Nav:GetMask() 
    Nav:SetMask(MASK_*)
    

    Revisit the first post for function descriptions and some new images.
    The example file has also been updated.
    Reply With Quote Edit / Delete Reply United States Show Events Lua King Lua King x 1 (list)

  31. Post #31
    deluvas's Avatar
    September 2006
    85 Posts
    Thanks

  32. Post #32
    foxcock
    Bletotum's Avatar
    June 2008
    6,873 Posts
    With the current version of the module, I get this.


  33. Post #33
    Gold Member
    Spacetech's Avatar
    January 2006
    510 Posts
    With the current version of the module, I get this.

    What are you doing to get that? Did it create any crash dumps?
    The only time I ever got that was when I removed the distance limit to the alt key node viewing, so many nodes were in view that gmod just crashes.
    Reply With Quote Edit / Delete Reply United States Show Events Lua King Lua King x 1 (list)

  34. Post #34
    Gold Member
    Silverlan's Avatar
    October 2005
    745 Posts
    What are you doing to get that? Did it create any crash dumps?
    The only time I ever got that was when I removed the distance limit to the alt key node viewing, so many nodes were in view that gmod just crashes.
    I've been getting the error a couple of times too, only when using the module serverside though. Can't say when exactly the error shows up, it seems to be random. Sometimes when trying to load the nodegraph from a file, sometimes even just after calling CreateNav().

    Here are the crashdumps:
    http://filesmelt.com/dl/gm_navigation_crashdumps.rar

  35. Post #35
    foxcock
    Bletotum's Avatar
    June 2008
    6,873 Posts
    Then what part of the module can be done serverside? More specifically, what must NOT be done serverside?

  36. Post #36
    deluvas's Avatar
    September 2006
    85 Posts
    Confirmed. It randomly freezes on the server side...

  37. Post #37
    Gold Member
    Spacetech's Avatar
    January 2006
    510 Posts
    Confirmed. It randomly freezes on the server side...
    Do you have it loaded clientside and serverside while playing on a local server?
    Reply With Quote Edit / Delete Reply United States Show Events Lua King Lua King x 1 (list)

  38. Post #38
    sk89q's Avatar
    December 2009
    362 Posts
    Very nice! It would have made my Stranded gamemode-playing bot work so much better.

    Would it be possible to have the generation threaded and also use more processors?

    On another note, on gm_construct, it only climbed a ramp half-way. How well does it handle ramps and stairs?

  39. Post #39
    Gold Member
    Spacetech's Avatar
    January 2006
    510 Posts
    Very nice! It would have made my Stranded gamemode-playing bot work so much better.

    Would it be possible to have the generation threaded and also use more processors?

    On another note, on gm_construct, it only climbed a ramp half-way. How well does it handle ramps and stairs?
    Depending on the grid size it might not go up some stairs and ramps. Your best bet is to add many walkable seeds around the map, when it navigates the map it will go from 1 walkable space until it runs out of room, to the next and so on.
    Reply With Quote Edit / Delete Reply United States Show Events Lua King Lua King x 1 (list)

  40. Post #40
    deluvas's Avatar
    September 2006
    85 Posts
    Do you have it loaded clientside and serverside while playing on a local server?
    I am using a dedicated server, and yes : I had them on both client and server.