Sun 30 Nov 2008 11:58:04 AM UTC, comment #10:
sorry, my fault: the errors were due to unresolved svn conflicts
|
Sun 30 Nov 2008 11:45:12 AM UTC, comment #9:
I get some compile errors with the latest SVN (1833):
../../src/stack.h:156: error: expected unqualified-id before »<<« token
../../src/stack.h:160: error: expected unqualified-id before »==« token
../../src/stack.h:167: error: expected unqualified-id before »>>« token
../../src/stack.h:364: error: expected unqualified-id before »<<« token
../../src/stack.h:370: error: expected unqualified-id before »>>« token
The full output of make is attached.
(file #16949)
|
Sat 29 Nov 2008 07:20:34 PM UTC, comment #8:
I've added a new interface into the Path object to get the number of turns it will take to reach a destination. This has yet to be used by the artificial intelligence routines.
Fixed in svn! Thanks.
|
Sat 29 Nov 2008 01:06:13 PM UTC, comment #7:
Hello,
I have made some progress on this bug. I have changed the shortest path algorithm to account for boat loading and unloading.
When a path is calculated, we calculate number of movement points to reach a given tile. The problem was that boat loading/unloading points were not taken into account -- and were given a weight of only 2 movement points, instead of the remainder of movement points the stack has.
In this patch the "moves left" are kept. Moves left is initially set to the number of movement points the stack currently has left, but when it gets exhausted it gets refreshed with one of two values: the maximum number of movement points the stack has when it is on land, or the maximum number of movement points the stack has when it is on water. This gives the proper weight to a boat loading/unloading tile.
When we hit unload or load into a boat, the "moves left" are exhausted, and we flip a boolean for whether or not we're in a boat.
The good news is that I have tested this algorithm with a scenario that fails with the old algorithm and succeeds with the new algorithm.
The bad news is that creating a new normal sized map with 80 cities takes 13 seconds with the old algorithm and 20 seconds with the new algorithm.
I have attached the patch. It isn't applied to svn yet, because I'm still looking for efficiencies.
Please apply this patch to svn head and try it out. I think you'll be pleasantly surprised.
(file #16941)
|
Tue 21 Oct 2008 12:22:21 AM UTC, comment #6:
Feel free to tinker with the code and try things out. If you get something that you think works satisfactorily, post a patch to this bug.
My way ahead would be to make a struct for every element of the distance array. Instead of only holding the total weight to this tile, it would hold which turn the stack is on, and how many movement points are left in the turn, and how many tiles we've crossed so far to get to this tile.
Various routines in lordsawar use the calculate method on the Path object to gauge how far away things are. Adding in extra movement points because of the ship load/unload penalty will exacerbate that situation. Another solution will have to be found for those callers: maybe by returning the number of tiles in the calculated path, or the number of turns that the path represents (e.g. 3.1 turns).
|
Tue 21 Oct 2008 12:16:03 AM UTC, comment #5:
Forget what I wrote about the distance array. I misunderstood it.
|
Tue 21 Oct 2008 12:12:13 AM UTC, comment #4:
> The weight of the tile that causes the ship loading/unloading penalty is a variable value that consumes the remainder of the movement points of the stack.
I don't think of that as a big problem, at least not for the sketched algorithm. There the "weight" is exactly the minimal number of movement points (mpts) to reach a tile: If you have the case land-->sea, it takes "2 + x - (i+2 mod x)" mpts to make the transition, where "2" is the minimum amount of mpts to board a ship, "x" is the stack's maximum number of mpts within a turn (a known value) and "i" is the known value of minimal mpts to reach the land tile.
Even a different number of movement points "x0" in the first turn can be handled:
if (x0 >= i+2) then return x0
else return 2 + x - ((i-x0)+2 mod x)
Concerning path.cpp: From the description, a "distance array" is used, but it should be a function. One could over-approximate the cost of sea travel to see if the distance array is really the main reason of the path finding problem.
|
Mon 20 Oct 2008 10:42:06 PM UTC, comment #3:
Thanks for the pseudocode, but the problem involves how to incorporate the feature into the lordsawar codebase at src/path.cpp:calculate. It is already doing a weighted exploration of the entire map to find the shortest path. The current algorithm only works with fixed values for weights; e.g. a forest tile is for a land-bound stack without a forest bonus costs the same amount every time. The weight of the tile that causes the ship loading/unloading penalty is a variable value that consumes the remainder of the movement points of the stack. Calculating the weight of the ship load/unload tile involves keeping track of how many moves the stack would have left at that point, while we conduct the shortest path algorithm.
When this feature is completed, a byproduct would be a method that can (reliably) determine how many turns a stack is away from it's destination. This will probably make the AI better... but the improvement in path finding probably represents an even bigger improvement to the AI.
|
Mon 20 Oct 2008 10:13:07 PM UTC, comment #2:
Well, it's a deficiency of the current path finding algorithm.
Have a look at the attached pseudo code and check if it makes sense to you and if it could be applicable for lordsawar. The idea is a parallel exploration of shortest paths starting from a point of origin.
(file #16714)
|
Mon 20 Oct 2008 06:28:57 PM UTC, comment #1:
WL2 has the same deficiency, and it is a source of frustration to gamers. The good news is that we have the freedom to fix this bug.
The bad news is that Lordsawar has cloned the deficiency.
I fear it is a difficult fix within lordsawar.
|
Mon 20 Oct 2008 05:48:53 PM UTC, original submission:
Either the path finding algorithm does not consider the correct cost of sea travel and/or it does not consider (longer) alternative routes that may use up less movement points.
Look out for the most northern Sirian city, called Pyronn, and a stack of 4 spiders that are about to cross a bridge. The saved path has been proposed by the path finding algorithm (SVN 1785).
|