 |
| |
|
|
brian32
|
|
This topic is about the code for the map AI that I'm working on. It is going to be geared toward the coding end of it, as opposed to the concepts end.
The coding will be in four main sections. These can be found in more detail in the Map AI Model page. The sections are as follows:
1) Define the borders of continents/bodies of water/etc.
2) Define "hotspots" (strategic points) within each of these continents/oceans/etc.
3) Divide the contintents into sections according to the hotspots and define the borders of each section
4) Determine the size of each section, nearby sections, inlets, outlets, strategic value, etc. for each section
This is obviously only a broad overview, and much more detail will be involved. I will periodically be posting code and tests on here as I make them. Any suggestions, contributions, criticisms, tips, etc. would be greatly appreciated.
[This message has been edited by brian32 (edited February 12, 2001).]
|
|
| |
|
|
|
brian32
|
|
Here is some skeleton code I made for how the continents will be assigned regions:
public class Regions
{
protected numberOfRegions = 0;
// Selects a random coordinate on the map
public getArbitraryPoint()
{
int x = math.random();
int y = math.random();
}
// Assigns the next region name to the random coordinate selected
public assignRegion( int x, int y)
{
MapLocation.region = numberOfRegions + 1;
this.numberOfRegions ++;
}
public floodFillRegion( int x, int y, int region )
{
//
// Algorithm to assign region number to all
// squares around the arbitrary point selected.
//
}
}
|
|
| |
|
|
|
LDiCesare
|
|
La Ferté sous Jouarre France
Jan 2001
time: 05:13
|
|
Hi all.
Mark's idea sounds good to me. The random part is used for the initial seeds. Just beware not tagging twice the same point.
The nearest neighbour should be implemented carefully though, because if you just use 4 or 8 adjacent squares as neighbours, you'll end up with many long vertical and horizontal borders, linked by a few 45 degrees sections. Using distance to initial seed gives more varied boundaries (Voronoi algorithm) and is probably better in terms of performance since you can go through the map only once.
|
|
| |
|
|
|
LDiCesare
|
|
La Ferté sous Jouarre France
Jan 2001
time: 05:13
|
|
Silly me. I didn't understand the topic. Now that I have read the model (I should have done that first) I
put new comments:
Why do you use random at all?
You could use an algo like start at squre (0,0), mark as 0 , then look (0,1): if same type (land/sea) mark as neighbor, else mark as newRegion (here 1).
Go on that way. When you are in (i,j) (i>0), you look at the various neighbors (3 on top, 1 on left): if all are of a different type, spawn a new region. If all are the same type and the same label, use the label. If there are several different labels for the same kind of terrain, you know that they are actually the same, so you can put whatever label for the current square, and store in a table the fact that the labels are only one region.
e.g. if 0 is sea, 1 is land on the following map (don't wrap borders here to make it simpler):
Left the map, then first stage labels, last, regions deduced:
00100011100 . 00122233344 00100033344
01110001001 . 01112223445 01110003443
01100001111 . 01122223333 (5=3) 01100003333
00110000101 . 00112222363 00110000303
00000110011 . 00000770033 (2=0,6=0) 00000770033
01001110000 . 08007770000 07007770000
01111100000 . 08887700000 (8=7) 07777700000
That way you flood-fill a whole map in one pass (I showed three images, but the third can be deduced from the second without going pixel-by-pixel).
That is interesting also because when restricting yourself to a subpart of a map (what is known to AI x) you could have trouble generating random seeds inside it. Here you can even mark "unknown" as one or more regions.
I hope this is more to the point.
[This message has been edited by LDiCesare (edited February 14, 2001).]
[This message has been edited by LDiCesare (edited February 14, 2001).]
[This message has been edited by LDiCesare (edited February 14, 2001).]
|
|
| |
|
|
|
brian32
|
|
Hi, everybody. Sorry for not making a post in a while.
An update of what I've been working on:
1) I've been expanding my skeleton code, taking into account your suggestions. I'll post some of it for you to see in a little while. I've run into a few minor problems so far. One of those is that we need to decide on a value for path intensity to determine what is a 'hotspot' and what is not. (If you don't know what I'm talking about, please read the Map AI model). Another thing is we need to decide what the most efficient way to do the floodfill will be. That will be a little tough to determine without a way to test the methods...
2) I've also been working on creating an interface to test my code. I would like to make something similar to the applet JimC created. However, I was unable to get his source code. I am not a very experienced graphical programmer, so any help in this area would be much appreciated.
As usual, I'm open to any suggestions or criticism.
|
|
| |
|
|
|
Mark_Everson
|
 |
Canton, MI
Jan 1970
time: 00:13
|
|
Hi Brian, thanks for the heads-up.
Well, I guess there are several criteria that are important in figuring out which the most important hotspots are. I'm not sure if I mentioned it yet, but I think the best use of the algorithm would have the modification in the bullet that has "suggested by Tim Smith" on the web page. That approach spreads out "path intensity" fairly efficiently IMO. So with that said... the really important hotspots should:
1. Be the ones that divide a region into sub-regions (otherwise they can just be gotten around some way) so a bonus should be given to hotspots importance if it divides a region into two sub regions. If the hotspots doesn't satisfy that condition then it shouldn't get the bonus.
2. Have a fairly large fraction of all paths going through them. Maybe we should start with 20% or more as a rule of thumb.
3. Big continents will need more hotspots kept track of than small ones. This will aid a lot in pathfinding.
So as a starting guess, you could write a function that takes the three considerations above, with some weighting between them, to figure out at what level you want to not bother with hotspots anymore. I could make something up on the spot, but given the fact that you are working with the topic directly, and can evaluate your ideas fairly quickly, I'd prefer to have you take a shot at it first  . If you get stuck, let me know and I'd be happy to help out.
I will try to get your Clash handle going soon. On the last set I had some trouble mailing Markos and Dan, so I'm going to wait for yours until it's clear they are getting my messages.
|
|
| |
|
|
|
brian32
|
|
I understood most of that already, I was just curious to see if people would have input as to what those actual values (like the bonuses and percentages) and weightings should be. I realize its not very important at this point and it can only be decided by testing, but I wanted to get people thinking about it so we can have some idea of what we want when the testing starts so it goes rather quickly.
It will be nice if right on the interface we could have a text box where we could put in the values of what decides hotspots. That would be much better than having to go in and change the code, then recompile, every time we want to test a new value. It shouldn't be very difficult and I will try to do it, but I'm not making any promises. Anyone else is welcome to help out.
|
|
| |
|
|
|
LDiCesare
|
|
La Ferté sous Jouarre France
Jan 2001
time: 05:13
|
|
Browsing the web, I found pages describing "influence mapping". That is very much like our model except it takes into account only the units. I think it could be used for a more tactical level AI:
Current model can give ideal goals, strategic, long-term, importance of terain, while influence mapping can help tell current strategical strengths and weaknesses. The algorithms seem very much alike.
What do you guys think?
|
|
| |
|
|
|
brian32
|
|
Nice to hear from you again, Jim. Thanks for sending that.
Good luck on your project.
|
|
| |
|
|
|
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.
|
|
| |
|
|
|
brian32
|
|
I think I get the basic idea. Just to make sure, though, a few details would be helpful.
|
|
| |
|
|
|
Mark_Everson
|
|
Canton, MI
Jan 1970
time: 00:13
|
|
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:
code:
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/ar.../article747.asp
Also Try: http://www.gamedev.net/reference/ar.../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/SiliconVal...4/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).]
|
|
| |
|
|
|
LDiCesare
|
|
La Ferté sous Jouarre France
Jan 2001
time: 05:13
|
|
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?
|
|
| |
|
|
|
LDiCesare
|
|
La Ferté sous Jouarre France
Jan 2001
time: 05:13
|
|
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
|
 |
New Zealand
Mar 2001
time: 17:13
|
|
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
|
|
Canton, MI
Jan 1970
time: 00:13
|
|
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/showthre...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.
|
|
| |
|
|
|
LDiCesare
|
|
La Ferté sous Jouarre France
Jan 2001
time: 05:13
|
|
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.
|
|
| |
|
| |
All times are GMT. The time now is 05:13.
Apolyton Time is 00:13. |
top of page
|
|
|
Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
|
HTML code is ON
vB code is ON
Smilies are ON
[IMG] code is ON
|
|
|
|
|
|
13-02-2001 07:12
. If we can do a good job on what we have planned so far, it will be, like you say, fairly straightforward to do the influence stuff.
|