[SOLVED] Game hangs - A* pathing related?

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
Posts: 48
Joined: Thu Jan 18, 2018 9:14 pm

[SOLVED] Game hangs - A* pathing related?

Post by milon » Thu Mar 15, 2018 2:13 pm

Hello, lovely community! It's that time again where I stumble across strange bugs and ask for your help. :awesome:

I've been slowly making progress with my RPG, and I'm currently working on creating roads between towns. Ultimately, I want roads built between some - but not all - towns. I've biased my A* implementation to heavily favor existing roads, otherwise the map becomes a huge mess of roads that don't utilize existing roads. Note that all map tiles are considered walkable for roadbuilding.

The problem? It hangs when I ask it to only apply some roads, rather than all of the potential roads. See the attached .love file. Here's the offending code, which comes from map.lua starting at line 319:

Code: Select all

	-- Calculate paths between Locations
	local paths = {}
	for i = 1, #nodeDist do
		local n1, n2 = nodeDist[i].n1, nodeDist[i].n2
		paths[i] = ai.pathfind(map, nodeDist[i].x1, nodeDist[i].y1, nodeDist[i].x2, nodeDist[i].y2)
		if paths[i] then
			local pointsTotal = nodeByID[n1].points * nodeByID[n2].points
			print("n1:"..tostring(n1).."\tn2:"..tostring(n2).."\tcost:"..tostring(paths[i].cost).."\tpoints:"..tostring(pointsTotal).."\tbuild:"..tostring(pointsTotal >= paths[i].cost))
--~ 			if pointsTotal >= paths[i].cost then
				for j = 1, #paths[i] do
					local x = paths[i][j].x
					local y = paths[i][j].y
					map[x][y].pathCost = map.roadCost
					map[x][y].feature = map[x][y].feature + 1
--~ 			end
With those two lines commented, it returns nearly instantly even on my rather elderly PC. When I uncomment them, it hangs immediately. I have no idea why it hangs. It's fine with the print statement, but it chokes when it's dropped into an if. At first I thought it was getting stuck because no existing roads meant extra work pathfinding - but that can't be right. When I modify the heuristic to care less about roads (line 126, increase avgCost to something like 1.5), it still does all the pathfinding in a snap, even though it's essentially making a new road for each location pair.


EDIT - I figured it out. It will also hang if I comment out map[x][y].pathCost = map.roadCost, which (eventually!) helped me figure out that previous roads were making later roads much more efficient to build - even though the end result was a TON of roads scattered across the map. That was a bad assumption on my part, lol. I've got lots of balancing to do with this, and some sections will have to go back to the drawing board.
(31.6 KiB) Downloaded 16 times

User avatar
Party member
Posts: 248
Joined: Sat Jan 16, 2016 10:30 am

Re: [SOLVED] Game hangs - A* pathing related?

Post by 4aiman » Sat Mar 17, 2018 4:26 pm

There's the jumper lib by Yonaba. It can save one lots of time :)

Posts: 48
Joined: Thu Jan 18, 2018 9:14 pm

Re: [SOLVED] Game hangs - A* pathing related?

Post by milon » Sat Mar 17, 2018 4:43 pm

Thanks for the suggestion. I did look at a number of them. I ultimately decided against jumper since it's mostly for straight - line stuff and didn't allow for varying "costs" in the terrain (IIRC - I looked at a lot of them). I want more curvy & natural paths, so it wasn't the best fit. But I've got it working very nicely now and I'm really happy with my A* implementation. When I've got more to show I'll post the new love file in my game thread.

Post Reply

Who is online

Users browsing this forum: Google [Bot] and 11 guests