[SOLVED] Game hangs - A* pathing related?

[milon]

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

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
			-- *** APPLY TUNNELS & FERRIES HERE ***
			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
--~ 			end
		end
	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.

Help?

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.

[4aiman]

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

[milon]

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.