generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Re: Improving Dijkstra's Algoritm

Previous Thread :: Next Thread 
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
20 Aug 2013 11:03 AM
on a side note:

How do I go about making it a navigation mesh..?
Report Abuse
trappingnoobs is not online. trappingnoobs
Joined: 05 Oct 2008
Total Posts: 19100
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
20 Aug 2013 11:19 AM
I have don't Dijkstra in school on paper and so I understand it better.
Report Abuse
digpoe is not online. digpoe
Joined: 02 Nov 2008
Total Posts: 9092
20 Aug 2013 11:25 AM
"I have don't Dijkstra"

Whaaa?

English please?
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
20 Aug 2013 11:25 AM
*I have DONE

Wrong key + spell check = fail
Report Abuse
digpoe is not online. digpoe
Joined: 02 Nov 2008
Total Posts: 9092
20 Aug 2013 11:28 AM
Mkay.
Report Abuse
stravant is not online. stravant
Forum Moderator
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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 is not online. stravant
Forum Moderator
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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 is not online. stravant
Forum Moderator
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
20 Aug 2013 12:14 PM
So you mean me being OCD with my part placement is beneficial to lag reduction..?
Report Abuse
stravant is not online. stravant
Forum Moderator
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
kirkyturky12 is not online. kirkyturky12
Joined: 30 Apr 2010
Total Posts: 1915
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
20 Aug 2013 12:24 PM
So do you have any hints for speed of my current implementation?
Report Abuse
kirkyturky12 is not online. kirkyturky12
Joined: 30 Apr 2010
Total Posts: 1915
20 Aug 2013 12:26 PM
Hmm, I haven't tested it yet, lemme do that now.
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
20 Aug 2013 12:27 PM
Yours is nice, but I would find it better if corners were allowed :P
Report Abuse
kirkyturky12 is not online. kirkyturky12
Joined: 30 Apr 2010
Total Posts: 1915
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
20 Aug 2013 12:32 PM
Mine is faster because of a small grid...
Report Abuse
kirkyturky12 is not online. kirkyturky12
Joined: 30 Apr 2010
Total Posts: 1915
20 Aug 2013 12:32 PM
Wait... What do all of the values in the nodeData table mean?
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image