Map AI coding

[brian32]

Hi, guys. I finally got back from vacation a couple of days ago, and then my internet wasn't working for some reason. Sorry... I'll get back to work on the code ASAP. I'm expecting a small demo of what I have done in a couple of days.

[Mark_Everson]

Excellent Brian!

We're going to need an A* adapted for isometric coordinates pretty soon also . The coord system is like in Civ2 with the x=0 column consisting of a zig-zagging column. If you don't understand what I'm saying here, let me know and I'll follow up with more detail.

[brian32]

I think I get the basic idea. Just to make sure, though, a few details would be helpful.

[Mark_Everson]

Sorry Brian, this request somehow fell below my radar. I have some stuff I can send you from home on details. Also if you do a web search on isometric coordinates, and look at the numbering system for the 'layered' version you'll know what the system is we need.

If you don't hear from me on this within a day or so, please email me, and that will remind me to send you the stuff.

I'm looking forward to the map AI demo too!

-Mark

[Mark_Everson]

Brian:

Here's the info on layered Iso coords:

Coords are just like the one used in civ2, where x=0 goes down on the map in a jagged vertical line.

So if you write coords in x/y pairs you have x,y on the tiles that looks kinda like this:

 0/0   1/0   2/0
    0/1   1/1
 0/2   1/2   2/2

So the three tiles that are leftmost in the 'code' section are the x=0 jagged column.

You can convert it to a Cartesian system thru a transformation. I will describe what you need to go from x,y (isometric) coords to u,v Cartesian coords. BTW, I believe these transforms are correct, but haven't proven them, or even checked them fairly exhaustively.

the transformations are:

u = x-y/2 and v = x+(y+1)/2 where y/2 is computed in an integer division sense so if y=3, y/2 =1

with the coords u,v you can now use the standard distance formulae for the distance between squares. What else do you need for the A*? I think distance between neighboring squares is it...

Note that this leaves you with the ordinary cartesian axes u, v at a 45 degree angle to the up-down right-left directions!

I'll also append here some coding/isometric tiles links. Most of these are largely concerned with graphics, but some may be of use to you.

Best source on isometrics is at gamedev, they have lots of iso tutorials andhow-tos http://www.gamedev.net/reference/list.asp?categoryid=44

Article I mostly used for graphics was: http://www.gamedev.net/reference/art...article747.asp

Also Try: http://www.gamedev.net/reference/art...article744.asp which
looks like a good intro though I haven't read it

Another is: http://www.voicenet.com/~krem/technical/isotiles.html
http://www.geocities.com/SiliconVall.../isonotes.html (some notes on a particular iso project, may be of value)


Let me know what else you need.

[This message has been edited by Mark_Everson (edited April 23, 2001).]

[Mark_Everson]

Brian:

Is anything happening on your end? We Really need the pathfinding code for units on the map Soon. Can you tell me if you're going to be able to make any progress in the next few weeks? If not, is what you have understandable so we can use it as a base for doing the TF pathfinding?

Thanks,

Mark

PS. BTW I just had a death in the family and will be out of touch for a while, so don't take it personally if I don't reply immediately to what you say .

[Gary Thomas]

I have coded the map AI algorithm and am currently testing it (it doesn't work yet!).

There appears to be a considerable gap in the various models in Clash. This relates to movement allowance. The path algorithm will be much more interesting when there are varied movement costs depending on terrain, and on the type of unit (wheeled or mounted units in mountains would have a severe penalty, for example).

If the information is available, I will be delighted to include this in D5.

Cheers

[Gary Thomas]

The map AI is now tested and working. However, the movement is not animated - the unit suddenly appears at its destination. I am working on that.

The next thing needed is some realistic terrain.

Cheers

[LDiCesare]

I can put in some info in the military units about move type. There should be at least three types of (ancient) unit types for moving:
Foot, mounted (including wheels-chariots, but that could be separate), and a mix of both.
More modern units would need to specify wheel-based, railroad-based (many cannons/artillery were mounted on rails during WWI), and maybe also some kind for all-terrain (4x4) wheeled/chain vehicles.
If you need me to correct other things in the military model for interfacing with the rest of the demo, I should do that first though (got my mail?).
Any ideas about terrain breakdowns vs unit specifics?
(road bonus greater for wheels, but how much, mountain malus lesser for foot-based, but how much?)
Should we make mountains impassable terrain for mounted/wheeled units unless there is a road?

[Gary Thomas]

Movement costs apply in two different situations. The tactical "on the battlefield" situation is different from the "on the march" situation. I am thinking, at present, only of the latter case.

I would assume that a task force would stay together, and hence would move at the speed of the slowest unit. So the "mixed" type would not be needed.

For strategic movement, I suspect that wheeled (ancient) units should be restricted to roads. The idea of a chariot or a siege engine going across country for any distance doesn't seem feasible.

In later days, even roads caused trouble for cannon (CS Forester's book "The Gun" has some good examples of this).

However, some terrain could be regarded as equivalent to a road. Salt pans, for example. It depends on how detailed we want to get. For the moment I am inclined to go for simplicity.

I am not clear in my mind exactly how the movement data should be stored. Although each unit should know how fast it is going, it then needs to know considerable detail about the actual terrain.

Cheers

[LDiCesare]

I was thinking of strategic movement too. Tactical is already modelled by "mobility" which is different from strategic movement.
I already have some tags as "canGoOnSea", so I can add a few ones. What I meant by mixed is that the TF will get the worst of all its components, which is also what you said. It won't come out as a separate type. I can try to make the units know which terrain they can walk on rather than have the terrain ask the units for something, but that should work only for multipliers for wheel/horse/foot, not the base terrain cost.

[Gary Thomas]

That sounds good. I assume that you will incorporate that data in the XML file?

I can't see why they can't include the base terrain cost as well.

I gather that your system doesn't have defined unit types built into the code - everything comes from the XML specification. Is that so?

The terrain won't ask for a movement allowance - the terrain is inert and inactive. However the moving unit can ask what terrain they are moving on, and return this, when asked, to the movement controller (activated by the GUI or the AI). There is one possible complication, involving exactly how the multiple "terrain" types in a single map square interact. I don't much like the present system where everything that can go in a square is "terrain".

To me the base is the underlying landform - mountain, flat, rolling, and so forth.

On top of this is "cover" - scrub, forest, grass, ice.

And on top of that are "features" - rivers, passes and such. Perhaps a volcano or two, for excitement.

These are the "natural terrain".

On top of the natural terrain are improvements - roads, towns, farmlands for example.

As far as movement is concerned, it is modified by all of these, as well as by two other very important factors - climate and weather.

Climate is what is normally there, and takes lattitude and season into account.

Weather takes into account the fact that we have a hurricane or blizzard right now, as examples.

As a passing thought, previous comments about "cities" seem to have been a little stuck in the Civ 2 system. There has not been, until the 20th Century, a 100km x 100 km city. What is much more typical is scattered villages, perhaps equalling a significant city in total population. A single square could easily have 100-200 villages, or 20-50 towns.

Cheers

[Mark_Everson]

Hi Guys:

I'm back, but barely functional due to things that have piled up to do at work and home while I was away

Most of the specs laid out look good to me, so I'll just make a few comments.

Cities are found in a square, they were never meant to Cover the square. City graphics for a large city can basically cover a square, but that's just for show.

Gary, here is some info on how movement is supposed to work. Its refered to as a 'tick' system as in ticks of a clock. I have grabbed an old post on the topic from the Military Model III thread. If you want to see the discussion around it, here's the url:

http://apolyton.net/forums/showthread.php?s=&threadid=12259&perpage=30&pagenumber=3

There is some info later in that thread on specific tick costs


Proposal for turn timeslicing system (ticks)

I have here first shot at a timeslicing system. Rather than refine it further, I thought I would present it and see what people think. Although I intentionally kept it somewhat simplistic, it may already be too complicated. That's one thing I would like People's input on. The thing I am really concerned about with this one is that the player won't always know whether they can move a TF to a particular square on a given turn without a substantial amount of calculation. One option of course is to just have the player try it and see if the move bounces, but that seems too cavalier. Anyway...

This system is designed so you can tell which TF does what, when and where. The result should be a rough mimicking of what would happen in actual continuous movements system, without much of the overhead involved. The basic idea is that each turn is divided into 10 ticks. Each action that a task force might undertake will have a cost in ticks, and when that cost is paid the unit will complete the action. This regimentation makes it possible to determine when reserves reach an area where combat is going to, or is likely to occur. I'll try and provide a quick example at the bottom. Note that it will occasionally be possible for experienced/hardened units to "break the rules" and squeeze in a few extra ticks per turn when the situation is sufficiently desperate.

Some of the more extreme actions take more than a turn worth of ticks. It's my intention that if orders are given, and not changed, then ticks can be saved up to achieve an action. This is true for even actions with much lower tick costs if they were "cut off" by the turn boundary. We will see how this works in practice. Additionally we need some mechanism to make sure TFs that happen to complete their movement actions on the same tick can't 'teleport' thru each other without ever covering the intervening space. This will be relatively easy to put in, we just need to decide on some specifics for implementations.

Mostly what I have so far relates to movement, although there is some other stuff. I think the system I have may already be too complicated, so ideas on how to simplify it with out losing the big effects are very welcome. All the tick costs below are additive. You just take all the relevant modifiers that apply and some them together. For each area I will list either the based tick costs or modifier, followed by a description that will hopefully clue you and is to what I'm talking about .

Basic terrain types
4 Flat (Grassland, steppe, flat desert)
6 Hills/Broken
10 Mountainous

- 1 Dirt Road
- 2 Hard Road (perhaps this bonus should only be for motorized vehicles)
+ 2 Obstructed Movement (Swamp, Jungle, Forest)
- 1 Any Type of Road through Obstructed Terrain Gives This Additional Bonus
+ 1 Cautious Advance (digging in every night, careful to always have scouts well in advance...)
+1 to +3 Artillery or other very slow movement item in TF
+1 to +4 Foraging for food (depending upon availability)
+1 to +4 Construct field fortifications (diminishing returns with more time spent)
+1 to +3 Flight Battle (normally on the low end of this)
+1 to +3 Pillage (depending on how much there is to wreck, somewhat diminishing returns)
+1 to Forever... Besiege

I will rely on the military guys to better specify especially the numbers that are given as ranges of tick costs.

All these modifiers assume movement across a square side. (At least the ones that are movement-oriented) for a diagonal move the tick cost is obtained by multiplying by 3/2 and rounding down.

Simple Examples
movement over flat land (4) with a dirt road (-1) with prepositioned supplies (+ 0) -- costs 3 ticks
movement in hilly (6), forested terrain (+ 2) while foraging (say + 2) -- costs 10 ticks

Example:

An ancient invasion. I can't come up with reasonable specifics right now because I'm under time pressure and want to post this, so I will just give a bland example for now. Let's say that a force from Carthage has invaded Roman territory. The Carthaginians, being low on food, and thinking there is no Roman army nearby, split up in order to forage more effectively. The two armies are in adjacent squares. The Roman army has been lucky enough to find out about this, and is going to attempt to attack the forces while they are divided. Let's say the Carthaginians have split evenly into the two forces, and that the Roman forces are equal in combat strength to the combined Carthaginians forces. Let's assume everything happens on Grassland with no roads and that the Romans have prepositioned supplies. We begin with the Carthaginians having split off, but having not yet forage for food. The Romans are in a square directly to the south of one of the Carthaginians TFs (on the right). We start the turn there.

Tick 1
both Carthaginians groups began to forage, they will be done at the end of tick 2
the Romans begin their movement into the Carthaginians square to the right, they will get there on tick 4
tick 2
both Carthaginians groups finish foraging, they are now set for food until the end of the turn.
Tick 3
Carthaginian group on the left begins moving into square on the right to reunite the armies, this takes 4 ticks, so they will arrive at the end of tick 6 (at this point they don't know the Romans are there) Carthaginian group to the right continues to forage waiting for the other group to return.
tick 4
Romans arrive in Carthaginian right square at the end of tick 4.
Tick 5
Square on Right Goes into Battle Mode. I think it's fair to say under these circumstances that the Romans will attempt to engage, and that the Carthaginians will attempt to delay or even withdraw in the direction of their compatriots. But the interesting point about the tick system here, is that if the battle were actually fought, we would know when the reserves would be showing up...
however, this isn't the battle module, so I'm not going to worry about what actually happens in the battle. All the tick system knows is that certain parts of the battle will take a certain length of ticks.
tick 6
at the end of tick 6 carthaginian 'left' shows up. This is either in the nick of time, or too late, depending how things have gone in the battle.

One other point... had the Carthaginian left square force been involved in some longer activity, it would have received word that a battle was imminent only when the Carthaginian right square forces detected the Roman's presence. The AI would then have to decide whether its mission were sufficiently important to go ahead, or whether its mission should be interrupted so it could attempt to support the Carthaginian right. In any case, I think we can assume that notification on an impending battle occurs on the tick after the discovery of enemy forces. That's because the messengers can move much faster than armies can, but without modern communications it would still take some time. For modern times with good communications, the notification would be instantaneous.

[Mark_Everson]

the list of proposed tick costs is in that same thread with the date:

09-09-2000 20:37

[LDiCesare]

Gary, yes it would go in the xml and yes everything comes from the xml file (though there is a fallback code with a limited set of units that were coded prior to the xml).
Currently I have <movement>2.5</movement>,
where movement is the allowed distance in one turn (over several ticks).
I think it should become something like:
<movement>
plains 4
rough 6
mountain 10
sea no
road -1
</movement>
where plains, rough, mountain are the basic movement cost for this kind of unit (typically all would be the same for airborne units, most often they would be the same for ground forces except maybe alpine troops and such).
All this would always use the default unit values unless overridden so that you don't have to write it all everytime.

Mark, I'll wait before putting foraging since we don't have supplies yet. However, I give orders to armies and these typically would take a certain number of ticks to do (either preset like foraging or not like go to square X, which may change as the map is uncovered).
As for figures, 1 turn is 10 ticks isn't it? I think cavalry could have a base of 3 in plains, and catapults would get +2 but a better road bonus (-2) if they can be cart-driven. Not thinking of modern units yet, but ultimately motored units on roads in plains could lower their cost to 1 tick. Is that reasonable?

I can also add data like <wheeled/> if that is relevant, but I think that all movement info can be formatted as proposed.

I'll change the move method which currently teleports to something where I expect to be called from one square to an adjacent square. I guess map AI can tell the next square needed to go to the final target.