## Optomizing a Dijikstra Map

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
ITISITHEBKID
Prole
Posts: 18
Joined: Tue Apr 24, 2018 7:37 pm

### Optomizing a Dijikstra Map

What are ways I can optimize this? I currently runs quite slow but I need it to be speedy.

Code: Select all

function love.load()
totale = 1

Can = love.graphics.newCanvas() --initialize canvas
cells = {}
maplist = {}
size = 20
msize = 25
creategrid(msize)
end

function love.draw()
love.graphics.setColor(1,1,1)
love.graphics.draw(Can,love.graphics.getWidth()/2,love.graphics.getHeight()/2,0,1,1,(msize*size)/2,(msize*size)/2) --draw canvas in center of screen. Using a canvas saves a lot of resources

end
Map initialization

Code: Select all

function initilize_map(goalindex,mapname)

for i=#cells,1,-1 do
mapname[i] = {value = math.huge}
--print(i)
end
if goalindex then
mapname[goalindex+1].value = 0
end

for i=#cells,1,-1 do
if mapname[i + 1] and cells[i].lines == cells[i+1].lines then
local vale = mapname[i + 1].value
if mapname[i].value >= vale+2 then
mapname[i].value = vale+1
end
end

if mapname[i - 1] and cells[i].lines == cells[i-1].lines then
local valw = mapname[i- 1].value
if mapname[i].value >= valw + 2 then
mapname[i].value = valw + 1
end
end

if mapname[i + msize] and cells[i].lines == cells[i+msize].lines -1 then
local vals = mapname[i + msize].value
if mapname[i].value >= vals + 2 then
mapname[i].value = vals+1
end
end

if mapname[i - msize] and cells[i].lines == cells[i-msize].lines +1 then
local valn = mapname[i - msize].value
if mapname[i].value >= valn + 2 then
mapname[i].value = valn+1
end
end
end
recalc_map(wall)

maplist[#maplist + 1] = mapname
love.graphics.setCanvas(Can) --set the canvas
for i,v in ipairs(cells) do --draw all cells because they have updated
love.graphics.setColor(cells[i].color)
love.graphics.rectangle("fill",v.x,v.y,size,size)
end
love.graphics.setColor(0,0,0)
for i=#cells,1,-1 do
--	if wall[i].value ~= 9999 then
love.graphics.print(wall[i].value,cells[i].x+3,cells[i].y+3)
--	end
end
love.graphics.setCanvas()--unset canvas

end
Map Recalculation

Code: Select all

function recalc_map(mapname)
for i=0,#cells do
if i == 0 then
i= 1
end
if mapname[i + 1] and cells[i].lines == cells[i+1].lines then
local vale = mapname[i + 1].value
if mapname[i].value >= vale+2 then
mapname[i].value = vale+1
end
end

if mapname[i - 1] and cells[i].lines == cells[i-1].lines then
local valw = mapname[i- 1].value
if mapname[i].value >= valw + 2 then
mapname[i].value = valw + 1
end
end

if mapname[i + msize] and cells[i].lines == cells[i+msize].lines -1 then
local vals = mapname[i + msize].value
if mapname[i].value >= vals + 2 then
mapname[i].value = vals+1
end
end

if mapname[i - msize] and cells[i].lines == cells[i-msize].lines +1 then
local valn = mapname[i - msize].value
if mapname[i].value >= valn + 2 then
mapname[i].value = valn+1
end
end
love.graphics.setCanvas(Can) --set the canvas
for i,v in ipairs(cells) do --draw all cells because they have updated
love.graphics.setColor(cells[i].color)
love.graphics.rectangle("fill",v.x,v.y,size,size)
end
love.graphics.setColor(0,0,0)
for i=#cells,1,-1 do
--if wall[i].value ~= 9999 then
love.graphics.print(wall[i].value,cells[i].x+3,cells[i].y+3)
--end
end
end
end

Creating the grid

Code: Select all

function creategrid(length)
local prevx = -size --start off with negative size, so when size gets added the first time the coords are 0
local lines = 0 --the y position
local why = lines * size
local max = length --the maximum amount of cells in one line
local starter
--print(length)
local total = length*length --the total number of cells there will be
local cur = 0 --the current cell, to tell when to go to next line
local roll = love.math.random(0,total)
while total > 0 do --while there are still cells that haven't been initialized

local color
if #cells == roll then
color = {0.25,0.7,0.4}
starter = #cells
else
color = {1,1,0.25} --YELLOW
end

cells[#cells + 1] = { --defining each cell
x = prevx + size,
y = why,
lines = lines,
color = color,

}
cur = cur+1 --once the cell is created the current goes up

prevx = cells[#cells].x --set prevx so the cell defining can figure out where its x is

if cur >= max then --if the current cell is greater then the maximum length of the grid
cur = 0 --the current cell is now set to the beginning 	again
prevx = -size --the size is reset so it starts from the second line
lines = lines +1	--the line is increased
why = lines * size
end

--print(num)
total = total-1 --As a cell has been initialized, the total can decrease by one
end
wall = {}
initilize_map(starter,wall)

end

Attachments
Dijkstra.love
Last edited by ITISITHEBKID on Wed Jul 18, 2018 3:59 pm, edited 1 time in total.

ivan
Party member
Posts: 1411
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

### Re: Optomizing a Dijikstra Square

Sure, setting up a profiler is a good starting point.
I ran it on your initialization code (love.load) and here are the results for "C" hooks:

Code: Select all

 +-----+----------------------------------+----------+--------------------------+----------------------------------+
| #   | Function                         | Calls    | Time                     | Code                             |
+-----+----------------------------------+----------+--------------------------+----------------------------------+
| 1   | (for generator)                  | 392502   | 10.653                   | [C]:-1                           |
| 2   | setColor                         | 392502   | 10.653                   | [C]:-1                           |
| 3   | rectangle                        | 391875   | 10.653                   | [C]:-1                           |
| 4   | print                            | 391875   | 10.644                   | [C]:-1                           |
| 5   | setCanvas                        | 628      | 10.653                   | [C]:-1                           |
| 6   | ipairs                           | 627      | 10.653                   | [C]:-1                           |
| 7   | type                             | 2        | 10.656                   | [C]:-1                           |
| 8   | floor                            | 1        | 10.656                   | [C]:-1                           |
| 9   | random                           | 1        | 10.656                   | [C]:-1                           |
| 10  | tonumber                         | 1        | 10.656                   | [C]:-1                           |
| 11  | __index                          | 1        | 10.656                   | [C]:-1                           |
+-----+----------------------------------+----------+--------------------------+----------------------------------+
Looks like the "time" is incorrect for C-calls via LuaJIT, but the number of calls should be accurate.
Nearly 400K calls to setColor, rectangle and print is a red flag.
You want to generate your map using pure Lua then draw it once.
Don't draw stuff during the generation.

Hooking Lua functions produces this:

Code: Select all

 +-----+----------------------------------+----------+--------------------------+----------------------------------+
| #   | Function                         | Calls    | Time                     | Code                             |
+-----+----------------------------------+----------+--------------------------+----------------------------------+
| 1   | random                           | 1        | 9.594                    | [string "wrap_Math.lua"]:37      |
| 2   | random                           | 1        | 9.594                    | g "wrap_RandomGenerator.lua"]:75 |
| 3   | creategrid                       | 1        | 9.594                    | main.lua:143                     |
| 4   | initilize_map                    | 1        | 9.593                    | main.lua:33                      |
| 5   | recalc_map                       | 1        | 9.575                    | main.lua:95                      |
| 6   | random                           | 1        | 0                        | g "wrap_RandomGenerator.lua"]:33 |
+-----+----------------------------------+----------+--------------------------+----------------------------------+
Doesn't provide us with a lot of useful information since your "recalc_map" function does "everything".
I would split that into separate functions (or at least make it recursive) so we can see where the inefficiencies are.
There is no way to optimize "everything".

I'll tell you right off the bat that your loops are not very clean.
I would use locals more efficiently (for example,

Code: Select all

cells[i]
is repeated multiple times).

ITISITHEBKID
Prole
Posts: 18
Joined: Tue Apr 24, 2018 7:37 pm

### Re: Optomizing a Dijikstra Square

ivan wrote:
Sat Jul 07, 2018 4:26 pm
~Snipped
Thanks a ton! I implemented a ton of fixes, and even removed recalc_map. Now it runs as smooth as butter.
Attachments
Dijskstra.love