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

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.

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.

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

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.

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.

Hope all is well

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!

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/articles/article747.asp

Also Try: http://www.gamedev.net/reference/articles/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/SiliconValley/Ridge/6444/isonotes.html (some notes on a particular iso project, may be of value)

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