Route Finding - Shortest Path

[whoward69]

"All roads lead to Rome"
(or Dublin in this case)
but some are shorter than others!

I've re-written my route finding code so that it can now find the shortest route between two plots by any given route type

Old "proximity to destination" method - takes the long route sometimes



New "shortest route" method



Just need to tidy a few things up, then I'll upload another version of the LiveTuner panel mod

 

[Killzerslaul]

Probably it's best to try and keep information about your mod to one thread, however great it is.

 

[Yakk]

Out of curiosity, what technique did you use -- A*?

 

[whoward69]

Out of curiosity, what technique did you use -- A*?

The code is fully commented, but copying the relevant bit

--
-- Find the shortest route between two plots
--
-- We start at the TARGET plot - as the path length from here to the target plot is 1,
-- we will call this "ring 1".  We then find all reachable adjacent plots and place them in "ring 2".
-- If the START plot is in "ring 2", we have a route, if "ring 2" is empty, there is no route,
-- otherwise find all reachable adjacent plots that have not already been seen and place those in "ring 3"
-- We then loop, checking "ring N" otherwise generating "ring N+1"
--
-- Once we have found a route, the path length will be of length N and we know that there must be at 
-- least one route by picking a plot from each ring.  The plot needed from "ring N" is the START plot,
-- we then need ANY plot from "ring N-1" that is adjacent to the start plot. And in general we need 
-- any plot from "ring M-1" that is adjacent to the plot choosen from "ring M".  The final plot in 
-- the path will always be the target plot as that is the only plot in "ring 1"
--
-- Returns the length of the route between the start and target plots (inclusive) - so 0 if no route
--

There is a more efficient method which generates rings alternately from both the start and target plots and looks for any plots in the intersection of the two outermost rings - however this requires an efficient method of performing the intersection (which is awaiting completion of some code which is on hold until I've updated all my mods to work with patch 332)

HTH

William

 

[killmeplease]

its called Wave algorhitm

 

[Yakk]

You might want to try A*.

Spoiler :

I'll do the "source->destination" version.

You maintain two collections of hexes.

The first are your "edge" hexes, the second are your "interior" hexes.

These are the region of the map you have searched to find the optimal route to your destination, as yet. "Edge" hexes completely surround the collection of "interior" hexes: all extending of our set happens at the edge, so keeping track of it makes sense.

The trick is that we keep the "Edge" hexes sorted by (Cost to get to the edge hex) plus (estimated cost to the destination). We are careful, and make sure that the (estimated cost to the destination) never overestimates the cost (so if it is possible for a hex to cost 1/10th of a unit of movement, the estimated cost is (strait line distance) / 10)).

However, if you are not using roads/railroads, the min cost per hex is 1, so you use that instead.

Each iteration of A* we take the "Edge" hex with the lowest sort value, and turn it into an interior hex.

The point of this is that in many cases, we end up biasing our search along the cheaper and more direct paths first. So instead of searching two large rings around both sides, we end up searching a "directed stab" towards the other location. Only if it runs into problems does it slide sideways around obstacles.

Each hex in our data structure stores the following information:
1: How much it costs to get here
2: What is the estimated cost to the destination
3: In the shortest route to get here, what is the previous hex?

...

You "seed" A* with an empty interior, and the original hex as your only "Edge" hex (with a flag saying that the previous hex doesn't exist).

To turn an edge hex into an interior hex, go over each of the neighbours. For each of them that isn't an edge hex or an interior hex yet, build an edge hex for it using this interior hex as its previous hex. (ie, take the cost to get here, plus the cost to enter that hex from here, and that is the cost of the new edge hex, and then calculate a new estimated cost to destination).

Once that is done, move the edge hex to the "interior" collection from the "edge" collection.

This algorithm terminates when the destination hex becomes an interior hex. To find the route, simply recursively ask for the preceeding hex from each hex until you reach the starting location.

Now, I'm not sure if lua comes with an efficient "container that is sorted" out of the box, which could be hard to write.

Note that variations on the above A* algorithm are pretty much the industry-standard for this kind of problem.

 

[Redox]

I tried to Google Wave Algorithm, but couldn't find a thorough description. Any sources?

I am currently working on a mod which requires pathfinding, so I have implemented an A* algorithm. I post a code below. It takes into account terrain costs/river crossings/embarking-disembarking, basically mimicking the game-engine pathfinding results. It is optimized for speed, so I hope it comes handy. It is also thoroughly tested (and used) by me. I wasn't sure if anyone would be interested in pathfinding, so didn't post it here in the forums.

Code:

local mapMaxX, mapMaxY = Map.GetGridSize();
local mapMaxXX = mapMaxX;	--DB
local mapWrapX = Map.IsWrapX();


--DEBUG_ITERDATA={};
--DEBUG_CNT=0;
function AStar_AddToSet(set, x, y, G, H)
	local plotID = x + y * mapMaxX;
	if(set[plotID]==nil) then
		set[plotID]={};
	end
	set[plotID].x = x;
	set[plotID].y = y;
	set[plotID].G = G;
	set[plotID].H = H;
	set[plotID].F = G + H;
	return set, plotID;
end

function AStar_HeuristEst(x1, y1, x2, y2, calc, epsilon)
	return calc and (Map.PlotDistance(x1, y1, x2, y2) * epsilon) or 0;
end

function AStar(x1, y1, x2, y2, saturate, moves, moves_reserve, unitstat, zocmap, terrainCostMap)
	local timeStart = os.clock();
	
	if(moves_reserve == nil) then moves_reserve=-1000; end
	
	if(unitstat == nil) then
		unitstat={};
		unitstat.domain = DomainTypes.DOMAIN_LAND;
		unitstat.maxMoves = moves;
		unitstat.ignoreCost = false;
		unitstat.enterImpass = false;		
		unitstat.coastal = false;
	end
	
	--local heuristicsEpsilon = 1.2;	--this gives [almost] optimal path and significantly reduces the number of searches performed
	local heuristicsEpsilon = 1;	--1 gives always ideal solution
	local target = nil;
	
	if(saturate) then 
		x2=-1; 
		y2=-1;
		heuristicsEpsilon = 0;
	else
		target = (x2 + y2 * mapMaxX);
	end
	
	local fail=true;
	
	local ClosedSet={};
	local OpenSet={};
	local DeadSet={};
	local source;
	
	OpenSet, source=AStar_AddToSet(OpenSet, x1, y1, 0, AStar_HeuristEst(x1, y1, x2, y2, not saturate, heuristicsEpsilon));	--add point of origin
	OpenSet[source].moves = moves;
	
	local OpenHeap;
	OpenHeap = HeapCreate(OpenHeap);
	OpenHeap = HeapInsert(OpenHeap, source, OpenSet[source].F);
	
	local Prev={};

		--[[DEBUG_CNT=-1;	---DB	
		DEBUG_ITERDATA={};	---DB ]]--
	
	while true do
		
			--[[DEBUG_CNT=DEBUG_CNT+1;				--DEBUG
			DEBUG_ITERDATA[DEBUG_CNT]={};
			DEBUG_ITERDATA[DEBUG_CNT].OpenHeap=tcopy(OpenHeap);
			DEBUG_ITERDATA[DEBUG_CNT].OpenSet=tcopy(OpenSet);
			DEBUG_ITERDATA[DEBUG_CNT].ClosedSet=tcopy(ClosedSet);
			DEBUG_ITERDATA[DEBUG_CNT].Prev=tcopy(Prev);			-- ]]--
		
		--remove from open set
		local tmp_Fval, lowestF;
		OpenHeap, tmp_Fval, lowestF = HeapDeleteBest(OpenHeap);
		
		if(lowestF==nil) then 	--all saturated
			fail=not saturate; 
			break; 
		end;
				
		--[[print("");		
		print(DEBUG_CNT,"LowestF:",lowestF,tmp_Fval);	
		
			DEBUG_ITERDATA[DEBUG_CNT].lowestF=lowestF;
			DEBUG_ITERDATA[DEBUG_CNT].lowestF_F=tmp_Fval;	--]]--
		
		--add to closed set
		ClosedSet[lowestF] = tcopy(OpenSet[lowestF]);	
		local lowestF_x = ClosedSet[lowestF].x;
		local lowestF_y = ClosedSet[lowestF].y;
		local lowestF_G = ClosedSet[lowestF].G;
		local lowestF_moves = ClosedSet[lowestF].moves;
		--print("LowestF:",lowestF,lowestF_G,ClosedSet[lowestF].moves);
		
		OpenSet[lowestF] = nil;	
	
		if(lowestF==target and not saturate) then 	--reached target
			fail=false; 
			break; 
		end;
		
		--Events.SerialEventHexHighlight( ToHexFromGrid( Vector2( lowestF_x, lowestF_y ) ), true, Vector4( 0, 0, 1, 1 )); 	
		--EnvelopeSet[lowestF] = nil;	
		
		lowestFPlot = Map.GetPlot(lowestF_x, lowestF_y);
		if(lowestFPlot~=nil) then
		
			local movesLeft = lowestF_moves;
			if(not saturate or movesLeft > 0) then --when saturating, we only care about how far we can reach in a single turn
				
				movesLeft = (movesLeft <= 0) and unitstat.maxMoves or movesLeft;	--if not saturating, we should take into account move "reloading" every turn.
				
				--loop over 6 neighbor plots
				local oddCorr = (lowestF_y % 2 == 0) and -1 or 1;	--correction for odd rows displacement
				for i=0,1 do
					for j=-1,1,1 do
					
						local xCorr = ((i~=0 and j~=0) and oddCorr or 0) + ((j==0) and (i*2-1) or 0);
						local neighborX = lowestF_x + xCorr;
						if(mapWrapX) then 
							neighborX = neighborX % mapMaxXX; 
						end
						local neighborY = lowestF_y + j;
						
						--Events.SerialEventHexHighlight( ToHexFromGrid( Vector2( neighborX, neighborY ) ), true, Vector4( 0, 1, 1, 1 )); 	
						
						local neighborID = neighborX + neighborY * mapMaxX;
						local extraTerrainCost = terrainCostMap ~= nil and terrainCostMap[neighborX][neighborY].val or 0;
						
						--make sure this neighbor is not in ClosedSet
						if(ClosedSet[neighborID] == nil) then
							
							if(OpenSet[neighborID] == nil) then
							
								local neighborPlot = Map.GetPlot(neighborX, neighborY);
								
								if(neighborPlot~=nil) then
									local neighborPlotFeatures = neighborPlot:GetFeatureType();
									local neighborPlotTerrain = neighborPlot:GetTerrainType();
									
									local neighborEnemy = zocmap ~= nil and zocmap[neighborX][neighborY].anchor > 0;
									if(neighborEnemy) then
										--add to closed set if there is enemy in that tile 
										ClosedSet = AStar_AddToSet(ClosedSet, neighborX, neighborY, 1000, 1000);
										DeadSet[#DeadSet+1] = neighborID;	--dead set is to clean impassable terrain from useful ClosedSet later
									else
										--see if tile is impassable
										local neighborImpass = (neighborPlot:IsMountain() or neighborPlotFeatures == GameInfoTypes.FEATURE_ICE or extraTerrainCost >= 1000);
										local completelyImpass = (unitstat.domain == DomainTypes.DOMAIN_SEA) and not
											((neighborPlotTerrain == GameInfoTypes.TERRAIN_COAST) or (neighborPlotTerrain == GameInfoTypes.TERRAIN_OCEAN and not unitstat.coastal));
										
										if(completelyImpass or (neighborImpass and not unitstat.enterImpass)) then
										--add to closed set if impassable 
											ClosedSet = AStar_AddToSet(ClosedSet, neighborX, neighborY, 1000, 1000);
											DeadSet[#DeadSet+1] = neighborID;	--dead set is to clean impassable terrain from useful ClosedSet later
											--print("Impassable. Add to closed set:", neighborX, neighborY);
											--Events.SerialEventHexHighlight( ToHexFromGrid( Vector2( neighborX, neighborY ) ), true, Vector4( 0, 0, 0, 1 )); 	
										else
											local neighborDrains = (unitstat.domain ~= DomainTypes.DOMAIN_SEA) and 
													(neighborPlotTerrain == GameInfoTypes.TERRAIN_COAST or neighborPlotTerrain == GameInfoTypes.TERRAIN_OCEAN);
													
											--add to closed set if drains moves and we are interested in single-turn pathfinding only
											if(neighborDrains and saturate) then
												ClosedSet = AStar_AddToSet(ClosedSet, neighborX, neighborY, 1000, 1000);
												DeadSet[#DeadSet+1] = neighborID;
												--print("Drains moves. Add to closed set:", neighborX, neighborY);
												--Events.SerialEventHexHighlight( ToHexFromGrid( Vector2( neighborX, neighborY ) ), true, Vector4( 0, 0, 0, 1 )); 	
											else
												local neighborAcrossRiver = lowestFPlot:IsRiverCrossingToPlot(neighborPlot);
												local neighborZOCMove = zocmap ~= nil and zocmap[neighborX][neighborY].val > 0 and zocmap[lowestF_x][lowestF_y].val > 0;
												local drainsNow = neighborDrains or (neighborAcrossRiver and not unitstat.ignoreCost) or neighborZOCMove;
												
												local neighborCost = 1;
												if(not unitstat.ignoreCost) then
													neighborCost = 1 + (neighborPlot:IsHills() and 1 or 0) + 
														((neighborPlotFeatures == GameInfoTypes.FEATURE_FOREST or neighborPlotFeatures == GameInfoTypes.FEATURE_JUNGLE or neighborPlotFeatures == GameInfoTypes.FEATURE_FALLOUT) and 1 or 0) + 
														(neighborPlotFeatures == GameInfoTypes.FEATURE_MARSH and 2 or 0) + extraTerrainCost;
												end
												
												local currCost = (drainsNow and movesLeft or neighborCost);
												local movesMinusCost = movesLeft - currCost;
												
												-- if saturating and reserve is required (for artillery to fire after moving), discard neighbors which drain moves
												if(not saturate or movesMinusCost > moves_reserve) then
													
													local tentative_G = lowestF_G + currCost;
													
													OpenSet = AStar_AddToSet(OpenSet, neighborX, neighborY, tentative_G, AStar_HeuristEst(neighborX, neighborY, x2, y2, not saturate, heuristicsEpsilon));
													OpenSet[neighborID].moves = movesMinusCost;
													OpenSet[neighborID].cost = neighborCost;
													OpenSet[neighborID].drains = neighborDrains;
													OpenSet[neighborID].impass = neighborImpass;
													
													OpenHeap = HeapInsert(OpenHeap, neighborID, OpenSet[neighborID].F);
													
													Prev[neighborID] = lowestF; --set F as previous node
													
													--Events.SerialEventHexHighlight( ToHexFromGrid( Vector2( neighborX, neighborY ) ), true, Vector4( 1, 0, 1, 1 )); 	
													--print("Add to open set:", neighborX, neighborY,"G:",tentative_G,"F:",OpenSet[neighborID].F);
												end
											end
										end
									end
								end
							else
								local neighborPlot = Map.GetPlot(neighborX, neighborY);								
								local neighborZOCMove = zocmap ~= nil and zocmap[neighborX][neighborY].val > 0 and zocmap[lowestF_x][lowestF_y].val > 0;
								local drainsNow = OpenSet[neighborID].drains or neighborZOCMove or lowestFPlot:IsRiverCrossingToPlot(neighborPlot);
								local currCost = (drainsNow and movesLeft or OpenSet[neighborID].cost);
								local tentative_G = lowestF_G + currCost;
								if(tentative_G < OpenSet[neighborID].G) then
									--update existing tile in OpenSet with better "predecessor"
									OpenSet = AStar_AddToSet(OpenSet, neighborX, neighborY, tentative_G, AStar_HeuristEst(neighborX, neighborY, x2, y2, not saturate, heuristicsEpsilon));
									OpenSet[neighborID].moves = movesLeft - currCost;
									
									OpenHeap = HeapUpdate(OpenHeap, neighborID, OpenSet[neighborID].F);
									
									Prev[neighborID] = lowestF;	--set F as previous node
									--print("Update open set:", neighborX, neighborY,"G:",tentative_G,"F:",OpenSet[neighborID].F);
								end
							end
						end

					end
				end	
			end	

		end
	end
	
	local bestPath = {target};
	local cnt = 1;
	while bestPath[cnt]~=nil do
		Events.SerialEventHexHighlight( ToHexFromGrid( Vector2( bestPath[cnt]%mapMaxX, math.floor(bestPath[cnt]/mapMaxX) ) ), true, Vector4( 0, 1, 0, 1 )); 	
		
		bestPath[cnt+1] = Prev[bestPath[cnt]];
		cnt = cnt + 1;
	end
	
	for i,id in ipairs(DeadSet) do
		ClosedSet[id] = nil;	--remove impassable terrain from ClosedSet
	end
	
	local timeEnd = os.clock();
	print("PATHFINDING TIME:",  timeEnd - timeStart );
	return (not fail), ClosedSet, bestPath, Prev;
end

function HeapCreate(heap)
	heap = {};
	heap.values = {};
	heap.values.first = nil;
	heap.values.last = nil;
	--pre-initializing values container with likely numbers, like 0,...,10 could reduce the number of insertions in-between
	--but I don't do it here
	heap.hash = {};
	return heap;
end

function HeapDeleteBest(heap)
	
	local bestPos=heap.values.first;
	local bestVal;
	local bestID;
	
	if(bestPos~=nil) then
		bestVal = heap.values[bestPos];
		local bestTab = heap[bestVal];
		bestID = bestTab[bestTab.last];		--For FIFO: set first here
			
		if(bestTab.count > 1) then
			--LIFO removal among identical elements. Results in depth-first behavior for A*
			bestTab[bestTab.last] = nil;			--For FIFO: set first here
			bestTab.last = bestTab.last - 1;		--For FIFO: set first here
			bestTab.count = bestTab.count - 1;
		else
			--remove whole container as it only has one value
			heap[bestVal] = nil;	
			--update sorted list of values
			heap.values[heap.values.first] = nil;
			heap.values.first = heap.values.first + 1;
			if(heap.values.first>heap.values.last) then
				--we have deleted the last value stored in heap
				heap.values.first = nil;
				heap.values.last = nil;
			end
		end
	else
		return heap, nil, nil;
	end
	
	--check validity of retrieved value
	if(bestID ~= nil) then
		heap.hash[bestID] = nil;	--clean hash
		return heap, bestVal, bestID;
	end
	
	--if value was invalid, retrieve another one (use tail call)
	return HeapDeleteBest(heap)
end

function HeapInsert(heap, id, val)
	
	if(heap.hash[id] ~= nil) then
		print("WARNING: trying to insert a value which already exists in table")
		return HeapUpdate(heap, id, val);
	end
	
	local index;
	if(heap[val] ~= nil) then
		index = heap[val].last + 1;
		heap[val][index] = id;
		heap[val].last = index;
		heap[val].count = heap[val].count + 1;
	else

		local a = heap.values.first;
		local b = heap.values.last;
		
		if(a == nil) then
			heap.values.first = 1;
			heap.values.last = 1;
			heap.values[1] = val;
		elseif(val < heap.values[a]) then
			local insSpot = a - 1;
			heap.values[insSpot] = val;
			heap.values.first = insSpot;
		else
			--Value val got to be inserted somewhere in the middle or the end
			local ii = heap.values.last;
			while heap.values[ii] > val do
				heap.values[ii+1] = heap.values[ii];
				ii = ii - 1;
			end
			heap.values.last = heap.values.last + 1;
			heap.values[ii+1] = val;
		end

		--this value didn't occur yet. Create a container for it
		index = 1;
		heap[val] = {};
		heap[val].first = 1;
		heap[val].last = 1;
		heap[val].count = 1;
		heap[val][index] = id;
		
	end
	
	heap.hash[id] = {};
	heap.hash[id].val = val;
	heap.hash[id].pos = index;

	return heap;
end

function HeapUpdate(heap, id, newval)
	--potential duplicate entry is stored in heap until retrieval.
	--at retrieval, if value is invalid (nil), the value is discarded and next one is retrieved
	--because retrieval is always from first position, it is much cheaper to discard then instead of discarding it now from the middle
	local hashInfo = heap.hash[id];
	heap[hashInfo.val][hashInfo.pos] = nil;
	heap.hash[id] = nil;	--clean hash so HeapInsert doesn't detect a duplicate entry
	
	heap = HeapInsert(heap, id, newval);
	return heap;
end

Example of use:

pUnit = UI:GetHeadSelectedUnit();
unitx = pUnit:GetX();
unity = pUnit:GetY();
currentMoves = pUnit:MovesLeft() / GameDefines.MOVE_DENOMINATOR;
targetx= targetPlot:GetX(); --where you want to go
targety= targetPlot:GetY();
saturateFlag = false; -- set true if you want to see all plots which unit can reach, not to go to particular target

local unitstats = {["domain"] = DomainTypes.DOMAIN_LAND, ["maxMoves"] = pUnit:MaxMoves() / GameDefines.MOVE_DENOMINATOR, ["ignoreCost"] = pUnit:IgnoreTerrainCost(), ["enterImpass"] = pUnit:CanMoveImpassable(), ["coastal"] = false};

local successFlag, ClosedSet, BestPath, ParentMap = AStar(unitx, unity, targetx, targety, saturateFlag, currentMoves, nil, unitstats, nil, nil);

BestPath output table will contain the optimal path, in the format of plotIDs (plotID = x + y * mapGridMaximumX)

I copied the functions from live code, so I hope I didn't forget to include anything.

 

[killmeplease]

A* is much faster than wave
so i think its not needed to you really

 

[Redox]

Yeah, I think I found it under the name of wavefront algorithm. It seems to be used for routing in electronic circuits, maybe it's better than other algorithms for that? But for pathfinding on the terrain A* seems to be recognized as the fastest. I'm not a specialist in this though.

 

[killmeplease]

it also known as Lee algorithm
http://users.eecs.northwestern.edu/~haizhou/357/lec6.pdf

lee algorithm guarantees that the shortest way will be found but it is very much slow in comparison to A*

 

[Redox]

This is helpful, thanks. The presentation mentions about 5 algorithms for "maze routing" and "line search", and none of them are mentioned in http://en.wikipedia.org/wiki/Pathfinding. I guess maze routing is different from pathfinding, because you have lots of connections on electronic circuit which have to be optimized relative to each other. Otherwise I am wondering why those algorithms would be used at all.

 

[killmeplease]

A* does not provide 100% accuracy afaik
performance is vital for games whereas its not a main thing for CAD programs

 

[Redox]

I see, that would make sense. What I know about A* I read on Wikipedia, and somehow I thought it finds an optimal solution, but can't now find a place in the article where it would say so. So, maybe it doesn't. In all of my pathfinding tests it found the shortest possible path though.

There is a more efficient method which generates rings alternately from both the start and target plots and looks for any plots in the intersection of the two outermost rings - however this requires an efficient method of performing the intersection

Actually, the efficient method of intersecting sets is something that I could very much use. If you have came up with one, please share. Unless it's totally implementation-dependent of course.

 

[SamBC]

Part of the issue with A* is that the quality of results (and performance) depend on the quality of the heuristic. Using it for CivV, I imagine that the actual routing would consider terrain costs, but the heuristic wouldn't (couldn't), meaning it wouldn't have the guarantee the heuristic is supposed to have (h(plot) <= length_of_shortest_possible_route_from(plot)), as some transitions have move cost of less than 1 per hex. I suppose the heuristic could be restored to the guarantee by making it assume that a direct route will be along roads/rails, but that's just equivalent because it's a linear adjustment. So the required guarantee is effectively present, but it's flawed in this case. A* is slow (but not too slow) to consider routes that take a detour to produce a cheaper route, as it checks most-direct routes first. Of course, it may be that a novel heuristic function is possible.

Another possible adjustment is to keep a table of accelerated route fragments (ie paths along roads/rails) to use in place of single-hex transitions where available.

 

[Redox]

Actually, roads/railroads are the only thing my algorithm doesn't take into account yet. Without them the minimum move cost per tile is 1, and I use a simple "count plots between us and the goal" as the heuristic, so it always satisfies that inequality.

But then if I want to take into account the roads, I could just divide my heuristic by 5 or so. Then it will satisfy the inequality, but will become useless for pushing the search in the direction of the goal. I think I get it.

I like the idea of keeping a table of roads I will need to think how to make A* use that table in a cheap way though. Thanks for the insight

 

[Yakk]

It will still push the search in the direction of the goal to a limited extent.

You'll go down roads "backwards" rather than towards the target to a large extent. You'll also go "backwards" (n-1)/n times as fast as you go forwards, where n is the road/railroad speed multiplier for the unit.

I've been playing with algorithms that do partial route caching using framed quadtrees, but memory costs are relatively high (for a 1000x1000 map, memory costs are measured in gigs), and updating it based on changes in the map is tricky (and the map effectively changes quite often with things like units moving around).

On the other hand, we get O(n) pathfinding that is perfect (where n is the length of the ideal path).

I really need to get the size of the cache down to something reasonable.

 

[Redox]

You'll go down roads "backwards" rather than towards the target to a large extent. You'll also go "backwards" (n-1)/n times as fast as you go forwards, where n is the road/railroad speed multiplier for the unit.

If heuristic is made very small, A* turns into vanilla Dijkstra's algorithm. So very small heuristic will still be useful for breaking ties (meaning when 2 neighbors have equal cost, which one do we follow first?). Encountering a railroad will be a tie, because you can go left (say, towards the goal) or right (away from the goal). Small heuristic will pick the correct direction.

I think where it will fail is when the goal is across the patch of rough terrain. Instead of stepping on the rough terrain it will explore a large number of open terrain plots backwards until heuristic for those plots becomes bad enough to surpass the difference in cost of stepping on rough and open terrain. Edit: I realize that this is what you meant by saying it will go "backwards" on the railroads

... memory costs are relatively high (for a 1000x1000 map, memory costs are measured in gigs)

I feel like my civ5 crashes frequently enough as it is

On the other hand, we get O(n) pathfinding that is perfect (where n is the length of the ideal path).

You mean, the algorithm ever includes only the "correct" plots into the closed set, but still has an Open Set which includes all their neighbors? Then this O(n) probably doesn't include the overhead of selecting the lowest-cost plot from Open Set to include into Closed Set, and adding neighbors to the Open Set. Also, if the cache is so huge, is there any computational cost involved in generating it?

 

[Yakk]

Naw -- its just a slightly more efficient way (than the naive N^2) to store the complete pathing information for a map using framed quadtrees that requires O(n) time to decode into an actual path. It takes roughly O(N^1.5) space, which gets prohibitive pretty quickly (hence the gigs of space problem).

The pathing information isn't cheap to build, but in some senses that doesn't matter (as it is a one-off cost). What I'm wrestling with is making updating the cache be cheap enough -- and it needs to be really cheap to be able to handle little things like units moving around! Possibly impossible, but impossible hobbies are the best kind.

 

[Redox]

I didn't realize your cache (quadtrees) contained complete pathfinding information from any point to any point. So, framed quadtrees are not just some particular storage method as I first thought.

What algorithm are you using to build your cache then? I'm curious about the topic. Without knowing anything about quadtrees I can't suggest much on how to update them. I would imagine for each plot they only store some "relative" data, like "I know my predecessor node and nothing else". Then any local change in terrain costs shouldn't require propagating changes in the cache further than the immediate neighborhood of plot for which the cost changed. I think that's what's done in Focused D* (as opposed to just D*). If your cache stores some data that's not relative to immediate neighborhood, then you might need to propagate changes throughout the cache, which is expensive. If you pointed me to some good material describing the method, I might be able to come up with something more specific.

 

[Yakk]

I'll continue in PM so as not to mess up this thread more. Sorry OP!