|
| 20 Aug 2013 11:00 AM |
Ok, so I just made my first working Dijkstra's algorithm but it will certainly be terrible. How can I go about improving it so that its cleaner and runs faster?
Code::
local nodeData = { A = {B = 4; C = 3;}; B = {A = 4; C = 2; E = 3;}; C = {A = 3; B = 2; D = 4; E = 11; G = 9;}; D = {C = 4; G = 9; H = 8;}; E = {B = 3; C = 11; F = 4;}; F = {E = 4; G = 1; H = 2;}; G = {C = 9; D = 9; F = 1;}; H = {D = 8; F = 2;}; }
local newTable = function(data) local tab = {} for i, v in next, data do tab[i] = {closed = false, last = nil, totalcost = math.huge} end return tab end
local notInTable = function(t, l) for i, v in next, t do if v == l then return false end end return true end
local getLowestConnection = function(node, list, open) for i, v in next, nodeData[node] do if not list[i].closed and list[i].totalcost > list[node].totalcost + v then list[i].totalcost = list[node].totalcost + v list[i].last = node --print(node,'->',i,'@',list[node].totalcost + v) if notInTable(open, i) then table.insert(open, i) end end end end
local getLowest = function(nodeList, openList) local current local lowest = 0 for i, v in next, openList do if not current or nodeList[v].totalcost < lowest then current = v lowest = nodeList[v].totalcost end end return current, lowest end
local pathfind = function(s, e) local startTime = tick() print(startTime) local list = newTable(nodeData) list[s].totalcost = 0 local open = {s} local finished = false repeat local currentNode local currentIndex local currentCost = math.huge for i, v in next, open do if list[v].totalcost < currentCost then currentNode = v currentIndex = i currentCost = list[v].totalcost --print(v, i, list[v].totalcost) end --[[local lowestNode, lowestCost = getLowest(list, open) --print(lowestNode, lowestCost) if not currentNode or lowestCost < currentCost then currentNode = lowestNode currentIndex = i currentCost = lowestCost end]] end --print(currentNode) if currentNode == e then finished = true else if not currentNode then error'NO NODE FOUND' end --print(currentNode) table.remove(open, currentIndex) list[currentNode].closed = true local connectNode, connectCost = getLowestConnection(currentNode, list, open) --print(connectNode) --[[table.insert(open, connectNode) list[connectNode].totalcost = list[currentNode].totalcost + connectCost list[connectNode].last = currentNode]] --print(currentNode,'->',connectNode,'@',list[connectNode].totalcost) end until finished local reverse = {e} local cNode = e repeat cNode = list[cNode].last table.insert(reverse, 1, cNode) until not cNode print(unpack(reverse)) end pathfind('A','H') |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 11:03 AM |
on a side note:
How do I go about making it a navigation mesh..? |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 11:16 AM |
Slightly off topic, but what caused you to choose Dijkstra's over, say, A*?
Not questioning your choice; I'm not well versed at all in path-finding and certainly not enough to comment on a decision, just curious. |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 11:19 AM |
| I have don't Dijkstra in school on paper and so I understand it better. |
|
|
| Report Abuse |
|
|
digpoe
|
  |
| Joined: 02 Nov 2008 |
| Total Posts: 9092 |
|
|
| 20 Aug 2013 11:25 AM |
"I have don't Dijkstra"
Whaaa?
English please? |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 11:25 AM |
*I have DONE
Wrong key + spell check = fail |
|
|
| Report Abuse |
|
|
digpoe
|
  |
| Joined: 02 Nov 2008 |
| Total Posts: 9092 |
|
| |
|
stravant
|
  |
 |
| Joined: 22 Oct 2007 |
| Total Posts: 2893 |
|
|
| 20 Aug 2013 11:50 AM |
@trapping
A* is basically just Dijkstra's + a heuristic function to bias the search in the direction of the goal, making the assumption that the majority of the movement will tend to be in the direction of the goal (You can construct cases where A* will take more time than Dijkstra's algorithm)
In fact, you can't even use A* in this case because there is no applicable heuristic function with which to bias the search. |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 11:59 AM |
| If I switched to an invisible network of parts, would magnitude from current to finish be a valid heuristic? |
|
|
| Report Abuse |
|
|
stravant
|
  |
 |
| Joined: 22 Oct 2007 |
| Total Posts: 2893 |
|
|
| 20 Aug 2013 12:04 PM |
| Yes, that is the usual heuristic. In this case you just have a graph of nodes with no particular meaning, so there is no heuristic to determine how "close" any of them is to the goal without actually doing a pathfind in the first place. |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:09 PM |
| On this: http://www.policyalmanac.org/games/aStarTutorial.htm it said that "Using whole numbers like these is a lot faster for the computer, too". Due to how all numbers in Lua (or, at least RBX_Lua) seem to be floats, does the same apply? |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:13 PM |
| Also, how often should I recalculate routes? Is once every 0.1 seconds good enough, or could I even use 0.5 (For the sake of argument I have up to 100 AIs at any given time)? |
|
|
| Report Abuse |
|
|
stravant
|
  |
 |
| Joined: 22 Oct 2007 |
| Total Posts: 2893 |
|
|
| 20 Aug 2013 12:13 PM |
Not at all. There is no benefit at all to using whole numbers in Lua.
There is however in some cases on Roblox: If you grid-align your constructions (to the 0.5 grid to be exact) they will go over the network faster because the game can send them as integers rather than floats at 1/2 the size. |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:14 PM |
| So you mean me being OCD with my part placement is beneficial to lag reduction..? |
|
|
| Report Abuse |
|
|
stravant
|
  |
 |
| Joined: 22 Oct 2007 |
| Total Posts: 2893 |
|
|
| 20 Aug 2013 12:14 PM |
| Dubious, but it is better with respect to join time. |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:16 PM |
| I am wondering if storing paths as "precalculated" once they have been done once would be better, so AIs in the same position at later times will just use that instead of doing the entire Dijkstra again. Do you think it would be very beneficial? I could then clear all precalculated paths if something changes :P |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:18 PM |
| Anyway, I have a real problem with finding tutorials on making a navigation mesh. Have you seen any useful tutorials/explanations of it? |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:20 PM |
My A* implementation: http://www.youtube.com/watch?v=Vk5cnya5OL8
My Dijkstra implementation: http://www.youtube.com/watch?v=tjQhVwHCszo
The pathfinders are actually quite quicker than they seem in the video, but the ROBLOX recorder is really slow and weird.
|
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:24 PM |
| So do you have any hints for speed of my current implementation? |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:26 PM |
| Hmm, I haven't tested it yet, lemme do that now. |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:27 PM |
| Yours is nice, but I would find it better if corners were allowed :P |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:30 PM |
| Well, your little example is certainly faster than mine. But then again, when working with actual parts, it would probably get slower. Lemme try to make your implementation work with my little grid thing and then we can see the real speed of it. |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:32 PM |
| Mine is faster because of a small grid... |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:32 PM |
| Wait... What do all of the values in the nodeData table mean? |
|
|
| Report Abuse |
|
|
|
| 20 Aug 2013 12:34 PM |
| nodeData is a table. Each index is the name of the node, each value is a table of connectors (format name=distance). |
|
|
| Report Abuse |
|
|