Optomizing a Dijikstra Map

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
ITISITHEBKID
Prole
Posts: 18
Joined: Tue Apr 24, 2018 7:37 pm

Optomizing a Dijikstra Map

Post by ITISITHEBKID »

What are ways I can optimize this? I currently runs quite slow but I need it to be speedy.
Love.load & love.draw

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
(1.42 KiB) Downloaded 139 times
Last edited by ITISITHEBKID on Wed Jul 18, 2018 3:59 pm, edited 1 time in total.
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Optomizing a Dijikstra Square

Post by ivan »

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

Post by ITISITHEBKID »

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
(1.5 KiB) Downloaded 129 times
Post Reply

Who is online

Users browsing this forum: Ahrefs [Bot], Majestic-12 [Bot] and 71 guests