Building units in a full city

Place to report bugs in MoM IME and suggest ideas for enhancements (please read rules before posting)
Virm
Posts: 63
Joined: Sat Sep 23, 2006 3:54 pm

Building units in a full city

Post by Virm » Sat Nov 24, 2007 6:45 am

So I noticed that in your changes planned for 0.93 there is this:

After a city builds a unit which makes a stack of 9 (or whatever the chosen maximum is), it should default production back to Housing and block you from building more units


except that in the original MoM, you could continue building units indefinately. So long as you did not change that city's production, at least. when you continue producing units in this manner the newly produced units overflow into the surrounding available spaces (see image). as each space reaches the maximum of 9, it starts filling the next square. any square occupied by something other than your own forces is skipped in this rotation. I don't recall (and haven't managed to create a scenario for it yet) what happens when all adjacent squares are occupied by other forces. I know that when all adjacent squares are used it starts in the top-left corner one more square out and goes around again. I've never seen this go beyond 2 squares out from the originating city, and I haven't really tried it yet.

So really I'm wondering if you'll implement this as the original MoM did or the way you've described? or will this become another server option (allow unit overproduction?)? the reason I ask is because the same rules apply to summoning a unit when the city holding your circle is fully occuped already.


Image

User avatar
Implode
Site Admin
Posts: 432
Joined: Fri Feb 24, 2006 3:35 am
Location: Newfoundland, Canada
Contact:

Post by Implode » Sat Nov 24, 2007 1:57 pm

I hadn't really thought about how to do it, I just knew its about time I got it fixed one way or another :)

Yeah I did realise the original MoM did that - but you also realise it won't let you change production, it greys out all the unit selections so while you can continue churning out the same unit you're already building, you can't switch? (or does it let you switch even though its greyed out?) So its pretty inconsistent.

Good point about summoned units, hadn't really thought about that - and it'd be no good if you spend ages summoning a Sky Drake only to get a "Sorry you've already got 9 spearmen in your city, so you lose your Sky Drake". So I guess I'll have to implement it like the original MoM... but still interested in your thoughts on the greyed out buttons?

Thanks,

Implode.

nazlfrag
Posts: 4
Joined: Tue Nov 27, 2007 8:35 am

Post by nazlfrag » Sun Dec 02, 2007 4:50 am

I'd say do it like the original, and have the greying out of units optional in server settings. It's simple enough to move a unit out and back to change production when it's greyed out anyway so I don't see it as a big issue if the buttons weren't greyed.

keithLaMothe
Posts: 6
Joined: Mon Feb 25, 2008 6:23 pm

Post by keithLaMothe » Tue Feb 26, 2008 2:25 pm

(edit: ack, didn't notice the last post's time, sorry for the thread revive)

Sounds good.

My guess is that it'd be simpler to not treat the "city.square.army.size = 9 case" as any different than < 9; i.e. don't gray out the unit buttons at all, and just offload production overflow into neighboring squares.

The one problem I see is in combination with the idea I saw somewhere else on here of allowing multiple-unit-production-per-turn from the same city. With a massive city with Inspiration on a ton of iron/coal and whatnot you might be able to churn out such hordes of spearmen that you'd be flooding 3-4 squares out and it'd be a challenge just to cut through all the re-popping units to get to the city. To handle that you could just not overflow any further away than 2 squares and drop any units that don't fit in that; not nice, but I guess it's a tradeoff.

Virm
Posts: 63
Joined: Sat Sep 23, 2006 3:54 pm

Post by Virm » Wed Feb 27, 2008 12:32 am

Then it's just a matter of planeshifting onto the offending city and removing the source of the problem. And one would think it not terribly difficult to simply look for the point closest to the city moving clockwise around the city from the top-left-most square. But then again, I may be wrong and it could be a complete pain to do.

keithLaMothe
Posts: 6
Joined: Mon Feb 25, 2008 6:23 pm

Post by keithLaMothe » Wed Feb 27, 2008 5:26 am

(edit: I figured in-for-a-penny-in-for-a-pound and updated the code block)

Good point about the planeshifting counter. Good ol' Astral Paratrooping ;)

And the algorithm wouldn't be too awfully painful:

The first step is building the list of possible tiles. Assuming you can reference a map tile by x,y coordinate (and plane coordinate, I suppose), you could do that by something like:

Code: Select all

(* type declarations *)
...
type
  CoordinatePair = class(TObject)
    X, Y: Integer;
end;

(* method declarations *)
...
function GetCoordinateOffsetMatrix(maxDistance: Integer) : TObjectList;
function GetValidTileForUnit(mUnit : MOMUnit; preferredX, preferredY, maxDistance : Integer) : CoordinatePair;
function TileHasRoom(x, y : Integer) : boolean;
function IsTileValidForUnit(x, y : Integer; mUnit : MOMUnit) : boolean;
procedure PlaceUnitOnTile(mUnit : MOMUnit; x, y : Integer);

(* implementations *)
...
function GetCoordinateOffsetMatrix(maxDistance: Integer) : TObjectList;
  var currentDistance, dX, dY : Integer;
      currentPoint: CoordinatePair;
begin
  result := TObjectList.Create;
  (* do each distance "layer" one at a time *)
  for currentDistance:=0 to maxDistance do
    (* for all x where abs(x) <= currentDistance *)
    for dX:=-currentDistance to currentDistance do
      (* for all y where abs(x)+abs(y) <= currentDistance *)
       for dY:=-currentDistance+abs(dX) to currentDistance-abs(dX) do
        (* exclude cases where abs(x)+abs(y) < currentDistance because those would be duplicates *)
         if abs(dX)+abs(dY) = currentDistance then
        begin
          currentPoint := CoordinatePair.Create;
          currentPoint.X := dX;
          currentPoint.Y := dY;
          result.Add(currentPoint);
        end
end;

function GetValidTileForUnit(mUnit : MOMUnit; preferredX, preferredY, maxDistance : Integer) : CoordinatePair;
  var i : Integer;
  var candidateTiles : TObjectList;
  var currentTile : CoordinatePair;
begin
  result:= nil;

  (* get offsets for all candidate coordinates within an acceptable distance *)
  candidateTiles := GetCoordinateOffsetMatrix(maxDistance);

  (* for each offset *)
  for i := 0 to candidateTiles.Count-1 do
  begin
    currentTile := CoordinatePair(candidateTiles.Items[i]);
    (* If TileHasRoom and IsTileValidForUnit return true, this tile can be used *)
    if TileHasRoom(currentTile.X,currentTile.Y) and IsTileValidForUnit(currentTile.X,currentTile.Y,mUnit) then
    begin
      result:= currentTile;
      break;
    end;
  end
end;


The order of tiles isn't quite right, but it does move out from the origin to the adjacent 4 tiles, to the next layer, to the next layer, etc... the order within a layer is weird.

Also, this depends on working implementations of TileHasRoom and IsTileValidForUnit, but obviously some kind of code exists in the current version for answering those questions.

The code that processes new unit production could use GetValidTileForUnit to get a valid coordinate pair for unit placement, or a nil value indicating that the unit cannot be placed.

I'd be happy to implement it, though the initial attempt may have the tile order different than original MoM, as noted above.

Virm
Posts: 63
Joined: Sat Sep 23, 2006 3:54 pm

Post by Virm » Wed Feb 27, 2008 8:20 pm

(Edit: That'll teach me to refresh the page before I post. Though a still relavent point is that original MoM will allocate units to spaces in a square pattern, top-left and clockwise. I'm leaving my code block unaltered.)

this all assumes that the x,y coordinates start 0,0 at top-left
to use your psuedocode, starting inside the 'begin'

Code: Select all

result := TPointList.Create;
   for currentDistance:=0 to maxDistance do
      dY:=-currentDistance
      for dX:=-currentDistance to currentDistance do
         result.Add(Point(x+dX,y+dY));

//at this point dX should still = currentDistance (I believe?)
      for dY:=-currentDistance+1 to currentDistance do
         result.Add(Point(x+dX,y+dY));

//and now dY is left at currentDistance
      for dX:=currentDistance-1 to -currentDistance do
         result.Add(Point(x+dX,y+dY));

//and now we traverse the last side with dX = -currentDistance
      for dY:=currentDistance-1 to currentDistance+1 do
         result.Add(Point(x+dX,y+dY));



this should produce the list of possible locations to place unit in, and in the same order that original MoM places them.

(forgive the comments in the code and any deviance from the intended language, I'm not a Delphi person yet)

keithLaMothe
Posts: 6
Joined: Mon Feb 25, 2008 6:23 pm

Post by keithLaMothe » Wed Feb 27, 2008 8:52 pm

Yea, my tile order is wacked out. My chief concern was starting with 0,0 (the city square) and moving out in distance order. Which isn't what MoM did. Thanks for working on your algorithm, which (I think) achieves the MoM behavior, at least with the nearby squares.

Taking a maxDistance of 3, the version in my post:

Code: Select all

    (* do each distance "layer" one at a time *)
    for currentDistance:=0 to maxDistance do
      (* for all x where abs(x) <= currentDistance *)
      for dX:=-currentDistance to currentDistance do
        (* for all y where abs(x)+abs(y) <= currentDistance *)
        for dY:=-currentDistance+abs(dX) to currentDistance-abs(dX) do
          (* exclude cases where abs(x)+abs(y) < currentDistance because those would be duplicates *)
          if abs(dX)+abs(dY) = currentDistance then
          begin
            currentPoint := CoordinatePair.Create;
            currentPoint.X := dX;
            currentPoint.Y := dY;
            result.Add(currentPoint);
          end


Gives these tiles when run in Delphi 7:

Code: Select all

0,0
-1,0
0,-1
0,1
1,0
-2,0
-1,-1
-1,1
0,-2
0,2
1,-1
1,1
2,0
-3,0
-2,-1
-2,1
-1,-2
-1,2
0,-3
0,3
1,-2
1,2
2,-1
2,1
3,0


Whereas the version in your post:

(adapted to Delphi 7)

Code: Select all

    for currentDistance:=0 to maxDistance do begin
      dY:=-currentDistance;

      for dX:=-currentDistance to currentDistance do begin
        currentPoint := CoordinatePair.Create;
        currentPoint.X := dX;
        currentPoint.Y := dY;
        result.Add(currentPoint);
      end;

      //at this point dX should still = currentDistance (I believe?)
      for dY:=-currentDistance+1 to currentDistance do begin
        currentPoint := CoordinatePair.Create;
        currentPoint.X := dX;
        currentPoint.Y := dY;
        result.Add(currentPoint);
      end;

      //and now dY is left at currentDistance
      for dX:=currentDistance-1 to -currentDistance do begin
        currentPoint := CoordinatePair.Create;
        currentPoint.X := dX;
        currentPoint.Y := dY;
        result.Add(currentPoint);     
      end;

      //and now we traverse the last side with dX = -currentDistance
      for dY:=currentDistance-1 to currentDistance+1 do begin
        currentPoint := CoordinatePair.Create;
        currentPoint.X := dX;
        currentPoint.Y := dY;
        result.Add(currentPoint);     
      end;
    end;


Gives these tiles:

Code: Select all

0,0
-1,1
0,1
1,-1
1,0
1,1
-1,-1
0,-1
1,-1
2,0
2,1
0,0
0,1
0,2
-2,-2
-1,-2
0,-2
1,-2
2,-2
3,-1
3,0
3,1
3,2
1,1
1,2
1,3
-3,-3
-2,-3
-1,-3
0,-3
1,-3
2,-3
3,-3
4,-2
4,-1
4,0
4,1
4,2
4,3
2,2
2,3
2,4


I think the first 9 tiles are correct, but I'm not sure after that (hard to visualize). Also, it yields a bunch of duplicates which isn't the end of the world (and might be due to my adaption of the algorithm), but I'd like to avoid. Finally, I don't know how a maxdistance of 3 yields an offset of 4,3 ;) I'm not sure I translated the algorithm correctly, I'll look more closely when I get the time.

edit: actually, upon visualizing, the first 9 tiles in the list I got out of the second algorithm aren't right:

Code: Select all

2 3 6
  1 5
7 8 4(9)


the (9) means that (+1,-1) is both the 4th and 9th tile. And it appears that (-1,0) is not generated at all.

the first tile list isn't much better, of course:

Code: Select all

        10
    08  04  12
06  02  01  05  13
    07  03  11
        09

Virm
Posts: 63
Joined: Sat Sep 23, 2006 3:54 pm

Post by Virm » Thu Feb 28, 2008 6:24 pm

I think the adaptation of my code followed an assumption of mine that the most recent value for dX or dY would be retained after ending a loop, but it looks like that might not be the case?

I think the algorithm I gave might also fail at distances less than one, so you might instead try:

Code: Select all

startPoint := CoordinatePair.Create;
startPoint.X := 0;
startPoint.Y := 0;
result.Add(startPoint);
for currentDistance:=1 to maxDistance do begin
      dY:=-currentDistance;

      for dX:=-currentDistance to currentDistance do begin
        currentPoint := CoordinatePair.Create;
        currentPoint.X := dX;
        currentPoint.Y := dY;
        result.Add(currentPoint);
      end;

      //at this point dX should still = currentDistance (I believe?)
      //  -  this was a wrong assumption.
      dX := currentDistance;
      for dY:=-currentDistance+1 to currentDistance do begin
        currentPoint := CoordinatePair.Create;
        currentPoint.X := dX;
        currentPoint.Y := dY;
        result.Add(currentPoint);
      end;

      //and now dY is left at currentDistance
      //  -  this was a wrong assumption.     
      dY := currentDistance;
      for dX:=currentDistance-1 to -currentDistance do begin
        currentPoint := CoordinatePair.Create;
        currentPoint.X := dX;
        currentPoint.Y := dY;
        result.Add(currentPoint);     
      end;

      //and now we traverse the last side with dX = -currentDistance
      //  -  this was a wrong assumption.
      dX := -currentDistance;
      for dY:=currentDistance-1 to currentDistance+1 do begin
        currentPoint := CoordinatePair.Create;
        currentPoint.X := dX;
        currentPoint.Y := dY;
        result.Add(currentPoint);     
      end;
    end;


and see if that gives better results?

keithLaMothe
Posts: 6
Joined: Mon Feb 25, 2008 6:23 pm

Post by keithLaMothe » Thu Feb 28, 2008 6:48 pm

I thought that was it. Delphi was giving some warnings about uninitialized values and I was going to look into that. Those variables are declared before those loops so I was thinking the values should persist. But I guess not.

Thanks!

Results:

Code: Select all

0,0
-1,-1
0,-1
1,-1
1,0
1,1
-1,0
-1,1
-1,2
-2,-2
-1,-2
0,-2
1,-2
2,-2
2,-1
2,0
2,1
2,2
-2,1
-2,2
-2,3
-3,-3
-2,-3
-1,-3
0,-3
1,-3
2,-3
3,-3
3,-2
3,-1
3,0
3,1
3,2
3,3
-3,2
-3,3
-3,4


I'll analyze when I get some time.

User avatar
Implode
Site Admin
Posts: 432
Joined: Fri Feb 24, 2006 3:35 am
Location: Newfoundland, Canada
Contact:

Post by Implode » Thu Feb 28, 2008 7:11 pm

Gee didn't know there was going to be a codewar on here ;)

IMHO to work like the original MoM I think it needs to do top-left first, then clockwise. I'm really sceptical about going out to a 2nd ring - this could mean a city on one island could produce units on a totally separate island, and detecting this to stop it would be tricky.

If you've got so many units that the whole first ring is full... then move some out of the way :)

BTW I don't just modify coordinates by +/- values, I always start from a position and move in a particular direction using a special routine which then copes with where the edges of the world map and different coordinate systems (like hex maps... I can't wait to try that one!) so it just needs to try in these directions out from the city:

8,3,3,5,5,7,7,1,1

and then give up. (1 is up, other directions numbered clockwise from there).

And for a really interesting discussion, I decided (too late) that attempting to number the coordinates (x, y, Plane) was a mistake in the first place because every routine has to have special cases for towers of wizardry. If I was starting from scratch, I wouldn't number the coordinates at all, I'd model the map as a network of nodes and connections, so most map cells have 8 connections to other cells. Map cells on the top/bottom edged only have 5. Towers of wizardry have 16 (you can just to any of the 8 positions on either plane). In that way a tower would literally be modelled as a single location. :)

Virm
Posts: 63
Joined: Sat Sep 23, 2006 3:54 pm

Post by Virm » Thu Feb 28, 2008 7:22 pm

actually the original MoM would work exactly like described by the code, including moving to a second ring (haven't tried a third yet) but will also produce land units on water squares without checks for if they can even be there. Those land units (on water) can then move onto any adjacent land spaces, but cannot move on water without a ship or some water-passing movement type. Humorously enough, these units can also be attacked on the water, but cannot move in combat. (and I believe in one of the versions of MoM it detected that they were land units, assumed they were in a ship, and didn't place them on the combat map. Thus causing an instant loss due to no defending units.)

In regards to doing the map as just a node network, wouldn't that make something of a pain to draw and track the map and it's visibility for the various players? (though I understand it's something of a pain as it is)

keithLaMothe
Posts: 6
Joined: Mon Feb 25, 2008 6:23 pm

Post by keithLaMothe » Fri Feb 29, 2008 5:34 pm

And for a really interesting discussion, I decided (too late) that attempting to number the coordinates (x, y, Plane) was a mistake in the first place because every routine has to have special cases for towers of wizardry. If I was starting from scratch, I wouldn't number the coordinates at all, I'd model the map as a network of nodes and connections, so most map cells have 8 connections to other cells. Map cells on the top/bottom edged only have 5. Towers of wizardry have 16 (you can just to any of the 8 positions on either plane). In that way a tower would literally be modelled as a single location.
A Node-edge based graph would certainly have flexibility advantages over an x,y,p coordinate plane for mapping. However, I think you would have to create a subclass specialized to handle some of the queries that MoM would require. Notably the "which nodes are in the city resource radius of this node" (used for existing cities or the surveyor). Iirc, the only native relationship existing in a pure node-edge graph between two nodes is "the shortest distance between us is x". There would have to be a specialization allowing for "named" edges, so you could have a node refer to it's "north" neighbor, "south" neighbor, etc.

Not insurmountable by any stretch, but it could get somewhat tricky.

Then again, I imagine this project has been nothing if not tricky.

Ste
Posts: 10
Joined: Mon Feb 19, 2007 1:02 am

Post by Ste » Sat Mar 01, 2008 9:36 pm

Nothing stops you from using two (or three, or even more) representations and using whichever is most appropriate for the task.

Virm
Posts: 63
Joined: Sat Sep 23, 2006 3:54 pm

Post by Virm » Thu Mar 06, 2008 1:10 am

Ste wrote:Nothing stops you from using two (or three, or even more) representations and using whichever is most appropriate for the task.


Except, of course, the need to keep every copy updated when anything changes in any of them (which, even when done carefully and efficiently, significantly increases memory usage and workload for the program). And if you want to avoid that problem, then you at least need to design a central storage form that everything else just references, so you would then be back to the original algorithm questions.

Post Reply