Map AI coding

[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.
//
}

}

[Mark_Everson]

Hi Brian:

I'm glad you're working on the map AI area! AI is something near and dear to my heart, and I think we can make Clash really unique in at least one way by doing a decent job with the AI.

If you're interested, you can also sign up as an official team member in the Team Members thread. It's probably near the bottom of the front page at this point.

I've only got one minor comment on what you have written so far. It occurs to me that using random locations to start the flood fill algorithm for continents etc. would be okay until you have most of the map identified. But using random locations to find that little one-square lake remaining to be identified could be exceptionally time-consuming. I have an idea for a fairly efficient algorithm... and it only uses things you'll need to code anyway mostly.

1. Start at some location on the map and tag it using the flood fill algorithm. I'll call this the "active" area.
2. For all boundary squares in the active area, initiate the flood fill algorithm on anything that's not marked, each in turn, giving you n additional areas. Once the active area has nothing unidentified next to it make each of these n "nearest neighbor" areas the active one.
3. Continue this process until the entire map is partitioned.

I think this should be much quicker than just doing it randomly...

[LDiCesare]

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.

[Mark_Everson]

Hi Laurent:

To clear up a possible misapprehension (although I may just be misunderstanding your post)... Brian is talking about the map Analysis routine for use on already-generated maps. That's completely distinct from map geration, which is what I thing you are talking about... That is why floodfill is ok.

For anyone who is interested the Map Generator Discussion is here: http://apolyton.net/forums/Forum21/HTML/000141.html . The thread is quite old, but it still represents where we are on map generation. Mca's old links in the thread don't work, but we still have the source code he did, and maybe the pix somewhere too...

[This message has been edited by Mark_Everson (edited February 13, 2001).]

[Lord God Jinnai]

I think istead of figuring out where land/water is, you should instead figure out where the continental shelfs are and the height of the land masses in a given area and then the water level.

The reason i say this is because several models depend on the continental shelf as opposed to the ocean floor and you'll need to figure out height eventually so in the long run it'll be easier IMO to do it this way.

[LDiCesare]

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).]

[Mark_Everson]

Yeah, your way might be more efficient, but mine wouldn't leave those messy holes in the numbering sequence

[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]

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]

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?

[Mark_Everson]

Agree. That has been in mind all along, but not written up . 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.

[JimC]

I've sent out my path intensity code now.... sorry for the delay in replying - i have my final yr project due in a couple of days time.

Hope all is well

Jim

[brian32]

Nice to hear from you again, Jim. Thanks for sending that.

Good luck on your project.