Topics

26

General discussion / GAE 0.2.12b

« on: 7 August 2009, 02:46:44 »

0.2.12b

Windows (32 bit)

Linux (32 bit x86)

A small data package is required, to be extracted in your glest directory (not needed if you downloaded it for 0.2.12a).

Complete list of changes

====================================================

0.2.12 Features:

The pathfinder defaults to the Greedy Search algorithm, with a node limit of 1024, both the algorithm and the node limit can be adjusted in the options menu.

LUA powered scenarios seem to work Ok, but this hasn't been tested extensively yet, please report any issues you find with it.

The new movement fields are,
any_water, unit may travel on any submerged cell.
deep_water, unit may only travel on deep submerged cells.
amphibious, unit may travel on any land or submerged cell.
There is a graphical glitch when an amphibious unit crosses the 'shore' (it 'jumps' up/down a bit).

A 'starting unit' with 'any_water' or 'deep_water' will probably crash the game, giving you a message about building a better map, this is because the unit couldn't be placed at the start location.  Amphibious units should be fine though.

Unit's can be spawned into the new fields from LUA, so while the only way to get a unit in the deep_water field in a regular game is with a morph (amphibious unit -> deep_water unit), in scenarios ships can be spawned in the water.

Please feel free to leave feedback and/or bug reports here, thanks!

27

General discussion / refactoring... goodbye UnitUpdater, and good riddance.

« on: 11 July 2009, 09:58:59 »

Status:

Changes:

Code: [Select]

UnitUpdater::updateStop()           ==> StopCommandType::update()
UnitUpdater::updateMove()           ==> MoveCommandType::update()
UnitUpdater::updateAttack()         ==> AttackCommandType::update()
UnitUpdater::updateAttackStopped()  ==> AttackStoppedCommandType::update()
UnitUpdater::updateBuild()          ==> BuildCommandType::update()
UnitUpdater::updateHarvest()        ==> HarvestCommandType::update()
UnitUpdater::updateRepair()         ==> RepairCommandType::update()
UnitUpdater::updateProduce()        ==> ProduceCommandType::update()
UnitUpdater::updateUpgrade()        ==> UpgradeCommandType::update()
UnitUpdater::updateMorph()          ==> MorphCommandType::update()
UnitUpdater::updateGuard()          ==> GuardCommandType::update()
UnitUpdater::updatePatrol()         ==> PatrolCommandType::update()

UnitUpdater::doAutoFlee   => MoveCommandType::doAutoFlee()
UnitUpdater::doAutoAttack => AttackCommandTypeBase::doAutoAttack()
UnitUpdater::doAutoRepiar => RepairCommandType::doAutoRepair()

UnitUpdater::repairableOnRange() => RepairCommandType::repairableOnRange()
UnitUpdater::repairableOnSight() => RepairCommandType::repairableOnSight()
UnitUpdater::searchForResource() => HarvestCommandType::searchForResource()
UnitUpdater::enemiesAtDistance()   => ??? not sure what I did with this one
UnitUpdater::updateAttackGeneric() => AttackCommandType::updateAttackGeneric()

UnitUpdater::attackerOnSight()   => CommandType::attackerOnSight()*
UnitUpdater::attackableOnSight() => CommandType::attackableOnSight()*
UnitUpdater::attackableOnRange() => CommandType::attackableOnRange()*
UnitUpdater::unitOnRange()       => CommandType::unitOnRange()*
* These could probably go in AttackCommandTypeBase ?

Functions Refined:
BuildCommandType::update()
HarvestCommandType::update()

Awaiting refinement:
RepairCommandType::update()
probably others ??

Original Post:
I've been doing some code surgery... The UnitUpdater was getting out of hand, and all those command updating methods were crying out to be stolen away and put in polymorphic Command classes...

unit_updater.cpp was 1699 lines, is now 796.

The various CommandType subclasses now override the virtual update() of CommandType, and that's where commands are now updated, not in the UnitUpdater.  It wasn't the cleanest of transplants, and could use some tidying, most of the CommandType::update() methods do a lot of reaching back into the UnitUpdater, but that can be sorted out easily enough now. Everything works, and it's much, much, much more manageable.

I've added a 'dummy' (do nothing) skill, and command for it, which can have costs and/or production attached.  This was at the request of Modman, and I actually had it working weeks ago, but I wasn't happy with how it worked... Once all this refactoring was done, it was very easy to hook it up and be (reasonably ) sure it would work as expected.

@Hailstone: I've merged the fixes from trunk, and everything from merge_3.2.2 into pathfinder... I thought it was ready to roll, but some more extensive last minute testing revealed big problems for size 2 units... I'll hopefully have that sorted tomorrow... if you're happy with the changes, we can copy it back to trunk, might as well test the path finder and new DummySkillType as well as LUA...

Edit:
I've moved the rest of the command related stuff from the UnitUpdater to CommandType and subclasses, and I've removed all references to the UnitUpdater from the CommandTypes.
I've 'tagged' the rest of 'unit_updater.cpp' with comments beginning //REFACTOR
with messages stating where I believe that chunk of code belongs...
@Hailstone : Have a look, let me know what you think...

28

General discussion / Ahoy there!

« on: 26 May 2009, 07:09:04 »

Forgive the crappy screen capture, but you get the idea...





Still lots of work to be done yet, but a good start...

29

General discussion / Fixing PathFinder::aStar()

« on: 8 May 2009, 02:41:15 »

Greetings.
This topic is intended for the (technical) discussion of Glest's pathfinder, and specifically what's wrong with it and how to fix it.
I've been pulling Glest's implementation of the A* algorithm apart over the past few days, so I'll start this off with a very terse description of  “standard” A*, and then have a look at the A* in Glest, and see if anything is amiss...

Edit: 20-May-09
This contains a couple of small errors that I'm too lazy to fix.
Edit: 9-June-09
Ok, I've fixed them... and cleaned up the pseudocode.

Standard A*
For a standard issue A* we need a node structure with 4 pieces of information, the 'distance' to here, the 'heuristic' (estimated distance to destination), a 'vector' that points back to the (currently) best known node to get here from, and of course we need the map co-ordinates.
The other thing we need is a function to calculate the heuristic, we will just use, as Glest does, the 'Euclidean' distance to the destination (using trusty old Pythagoras).
Also, I'm ignoring the extra cost of moving diagonally, to keep things simple (as Glest also does).
With the node structure and heuristic function at hand and two initially empty lists, named Open and Cosed, the standard issue A* algorithm goes as such,

start with startPos and destPos // Our start position and destination position
set startNode.position to startPos
set startNode.heuristic to Euclidean distance from startPos to destPos
set startNode.distance to 0
add startNode to Open List
while Open List is not empty
  select node from Open List with lowest distance + heuristic
  // let's call it minNode
  if minNode is destination
    we found a path! (Follow the vectors back to start pos)
  else
    for each adjacent node // let's call it newNode
      if newNode is not on Closed List
        if newNode is on Open List
          if minNode.distance + 1 < newNode.distance
            set newNode.distance to minNode.distance + 1
            set newNode.vector to point at minNode
          else
            do nothing
        else if minNode->newNode is a legit move
          add newNode to Open List  // diag = sqrt(2)?
          set newNode.heuristic to manhatten distance to destination
          set newNode.distance to minNode.distance + 1 // diag = sqrt(2)?
          set newNode.vector to point at minNode
        else
          do nothing
      else
        do nothing
    //end for
    Remove minNode from Open List, add to Closed List
  // end if
//end while
If we get here, Open List is empty, Failure  

So, basically in each loop iteration we pick the 'best' node from the open list, this is the node with the smallest distance + heuristic. If this best node is the destination, we have found our path. Otherwise, we look at each of this nodes neighbours in turn, ignoring any on the closed list, possibly updating them if they're on the open list, and adding them to the open list otherwise.

Glest's A*
Glest's node structure looks somewhat different, the 'distance' to here is not stored, and as well as the vector pointing back (indicating the best known path to here) there is a 'forward' pointing vector. This forward pointing vector is only 'filled in' once the path has been found though, so it has been omitted from this description.
Glest's nodes also have a CellExplored member which I'm ignoring here, and the path finder has a node limit built in, which again, I'm ignoring... this is the 'bare bones' of the algorithm.

start with startPos and destPos // Our start position and destination position
set startNode.position to startPos
set startNode.heuristic to Euclidean distance from startPos to destPos
add startNode to Open List
while Open List is not empty
  select node from Open List with lowest heuristic
  // let's call it minNode
  if minNode is destination
    we found a path! (Follow the vectors back to start pos)
  else
    foreach adjacent node // newNode
      if newNode is not on Open or Closed List
      and minNode->newNode is a legit move
        add newNode to Open List  // diag = sqrt(2)?
        set newNode.heuristic to Euclidean distance to destination
        set newNode.previous to point at minNode
      else
        do nothing
    // end for
    Remove node from Open List, add to Closed List
  //end if
//end while
If we get here, Open List is empty, Failure  

As can been seen, it's a bit simpler than standard A*. With no 'distance to here' the best node at each step is simply the one with the lowest heuristic. Glest's version also doesn't consider nodes already on the open list, the standard version checks to see if the path to the (open) node is better through the current (best) node, and updates it if so. So Glest's A* may not find the optimal path, but it should execute much quicker.

OK, I think that should just about be enough for anyone to take in at once
I've made some further discoveries and tinkered a bit, and with a very simple optimisation I've managed to reduce the 'worst case' calculation time for a path to about a quarter of what it was.
I'll need to get 'clean' copy of numerous source files to make a patch, but I believe I can improve performance further with some not to drastic changes, so I'll try that out first.
For the moment, I need to take pause, and gather my thoughts
more soon...