bugLordsAWar! - Bugs: bug #24618, shortest paths should consider...

 
 

bug #24618: shortest paths should consider ship loading/unloading movment penalty

Submitted by:  zed <savannah_zed>
Submitted on:  Mon 20 Oct 2008 05:48:53 PM UTC  
 
Category: gameSeverity: 3 - Normal
Item Group: NoneStatus: None
Privacy: PublicAssigned to: None
Open/Closed: Closed

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Sun 30 Nov 2008 11:58:04 AM UTC, comment #10:

sorry, my fault: the errors were due to unresolved svn conflicts

zed <savannah_zed>
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)

zed <savannah_zed>
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.

Ben Asselstine <benasselstine>
Project Administrator
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)

Ben Asselstine <benasselstine>
Project Administrator
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).

Ben Asselstine <benasselstine>
Project Administrator
Tue 21 Oct 2008 12:16:03 AM UTC, comment #5:

Forget what I wrote about the distance array. I misunderstood it.

zed <savannah_zed>
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.

zed <savannah_zed>
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.

Ben Asselstine <benasselstine>
Project Administrator
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)

zed <savannah_zed>
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.

Ben Asselstine <benasselstine>
Project Administrator
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).

zed <savannah_zed>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #16949:  make_errors.txt added by savannah_zed (4KiB - text/plain)
file #16941:  shortest.patch added by benasselstine (10KiB - text/x-diff - shortest path patch as of 29 Nov 08)
file #16714:  path.txt added by savannah_zed (2KiB - text/plain)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by benasselstine (Posted a comment)
  • -unavailable- added by savannah_zed (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 6 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sun 30 Nov 2008 11:45:12 AM UTCsavannah_zedAttached File-=>Added make_errors.txt, #16949
    Sat 29 Nov 2008 07:20:34 PM UTCbenasselstineOpen/ClosedOpen=>Closed
    Sat 29 Nov 2008 01:06:13 PM UTCbenasselstineAttached File-=>Added shortest.patch, #16941
    Mon 20 Oct 2008 10:13:07 PM UTCsavannah_zedAttached File-=>Added path.txt, #16714
    Mon 20 Oct 2008 06:28:57 PM UTCbenasselstineCategoryNone=>game
      SummaryPath finding: The cost of sea travel / alternative routes=>shortest paths should consider ship loading/unloading movment penalty

    Back to the top


    Powered by Savane 3.1-cleanup1