Map AI so far....

[JimC]

Path Intensity Algorithm Demo

Obviously some people care more than others about this area of the project, but this is my contribution so far....

I've had mixed reports about how well these Applets run - I personally can't get the Path Intensity Applet to run in a web browser at all, although it works using Sun's tools.

I've sent Java class files to those who I know can run them - if anybody else wants a copy just give me your e-mail address.

These are only partially complete - I'm hoping to make the tools as flexible as possible, to allow them to be used in map-development (if people think I'm heading in the right direction).

Any comments/questions/suggestions etc... ??

Jim

[Mark_Everson]

Others: For some background here is the basic idea Jim is working from.
home.akademie.de/~DToussaint/clash/map_ai.htm

Jim:
The applet is Great, really user friendly. Just for future reference, I didn't notice the sliders at the start and had trouble understanding the initial results until I said duh... (there's more map there!) The results were interesting and (fortunately) fairly similar to the expected.

Interesting things after about 30 min of playing around:

1) Did you include a penalty for previous paths crossing a square? I'll elaborate in (1') below.
2) I think we can get better results by first using a floodfill algorithm to identify and number all the land and sea areas. Then you only need look within each continent / sea or whatever for the path intensity.
3) Would it be too hard to put in the paths between random points as an option? I think this has some dangers associated with it, but it will also allow for identification of Important necks very quickly. You could just designate how many paths you want to do at the start.
4) A zoom-out mode so you can see the whole map w/out the slider bars would be nice too.


1') From the results of the applet I *think*
you didn't include one important element. I wrote about it on the Map AI web page and will quote it below. Specifically there are some large path intensities at the edges of interior features where the terrain is not all that strategically significant. Here's what I wrote on the web page...

[if you did include this part then I a) apologize, and b) don't quite understand the results]

"In addition to large weights at necks, this method will also give large values at the edges of interior features, for instance inland seas. Since such bands of large numbers of shortest path crossings aren't generally strategically significant (you can just move around the sea at a distance from
the shore, for instance) we want to give "pretty good" paths equal weights with shortest paths. Pretty good paths can be obtained by using a weighted A* algorithm. (Jim, I know you know this... this info just for the others) With an evaluation function f = g + xh where x >= 1 we change from shortest paths to simply pretty good ones. With this modification with x maybe 2 or so we'll get a random good path rather
than the shortest one.
Another way to accomplish this (suggested by Tim Smith) is to use previous "path intensity" (from previous paths crossing a square) as an additional cost of moving into the square. This will spread out "path intensity" across necks without significantly changing anything, and yet prevent shores of interior seas from racking up huge scores. This type of treatment will give results
like those shown in the figure above on the right side. "

I would use the method in the final paragraph of the quote to eliminate this difficulty. Essentially one should add a fraction, maybe 1/3, of a square's current path intensity to the cost to move through the square. This
will spread out the path intensity where there are a large number of nearly identical alternatives, and yet still produce high values at strategically important sites. Otherwise the AI units will IMO be continually garrisoning the edges of lakes or impassible mountain ranges thinking that they are strategically significant points!

BTW what are the terrain costs you're using. You can really see the effect with roads so they must be 3-4x better than plains at a guess.

Great Work!

-Mark


[This message has been edited by Mark_Everson (edited May 26, 1999).]

[F Smith]

I care!

I like it very much.

Work's pretty hectic right now, just opened a new phase of the project and the Senior VP wants a demo of the database query tool.

Sorry if I don't contribute much, but my mind's kinda swirling with SQL/JDBC stuff.

[Blade Runner]

JimC,

Wow!

1. I made a continent with a few lake inside. I got numbers on the surface of the water when I was looking for land path. Is this a bug or I misunderstand something?
2. Is there any possibility to draw the landmap and the intensitymap together?
Idea: you can cut the map squares half. One part can contain the original map value (land, road, etc..) the other half the intensity color code.
I was impressed with the system.

Blade Runner

[JimC]

OK some details:

current terrain values -

roads - 0.5
plains - 1.0
forest - 2.0
hills - 3.0
mountains - 5.0

the above are impassable to sea movement

ocean - 1.0
rough ocean - 2.0

the above are impassable to land movement

air movement is 1.0 for all squares
amphibious movement is combined land/sea movement (e.g. hovercraft)


The current algorithm consists of three main phases:

1- path calculation / counting
2- spreading / averaging iterations
3- 'standardising' vs a maximum value, at the moment this is 255 (8 bits)

I'll include options to turn 2/3 on or off so that users can see their effects more easily.

Mark:

1) You can modify the heuristic under 'Properties' - default value is 1.1 to give it a slight tug in the right direction

I can work on an option to increase terrain values based on path intensity, it may take a while though.

2) I'll think about it - again, it may take a while.

3) Easy - one of the main problems at the moment is that a node is 'lost' if it falls on impassable terrain. A random set of nodes could be forced to lie on passable terrain.

4) Easy


Blade Runner:

1) The spreading iterations basically involve each terrain square 'influencing' neighbouring squares. At the moment, impassable terrain is set at v.high resistance to change; however some spreading still occurs because IMO controlling ocean areas next to heavily travelled land areas is important for controlling that stretch of land (shore bombardment etc)

I'll make the 'resistance' of impassable terrain tweakable in my next version.

2) Easy


Anyone who cares to listen:

I'll make details of the algorithms more widely known once I've actually finalised them.

I'll release the source code of the MapNodeGenerator class as soon as I've commented / debugged it fully.

My goal is to make all values + assumptions fully adjustable by the user so that anybody can draw a map and 'play' with it.

Jim

[Glak]

Actually I think that the areas around interior lakes are strategically important and that you shouldn't try to get rid of that. They aren't as important as some other features can be but I think that they matter.

[Mark_Everson]

Hey Jim:

On my issue 1, I did try changing the heuristic, and it didn't change much. Yeah, the good point about doing my 2 is that for either water or land paths you can reduce the number of nodes significantly IMO. And reducing something that's to the fourth power is Big

-Mark

[JimC]

Latest demo version:

Path Intensity Applet

Changes:

Random paths are now an option - if this is selected, 300 random paths will be used to generate the results. All 300 pairs of nodes will be forced onto passable terrain (ensuring that they all get used), whereas with evenly spaced nodes this wasn't possible.

The spreading iterations / standardising steps can be toggled on and off, so that the raw data can be viewed.

btw Mark - I found a bug that caused the heuristic value to be ignored; changing the heuristic multiplier now has a clear effect. Higher heuristic values also speed up the process.

I'm still working on the other suggested improvements.

On a different note - performance issues. I've just upgraded to the hotspot JIT; with the old interpreter, I was getting around 10-20 paths per second. With hotspot I'm getting about 200-300 paths per second, and it still seems to improve every time I run it.

I suggest that we look into it....

Jim

[Druid2]

Wish I could go and look at it
*pout*

Am [trying] to use Win 95b & Netscape to do so, but *NYET*

[F_Smith]

Ya'll *must* get HotSpot.

Java at the speed of C.

Sorry, no more time!

Ciao.

[This message has been edited by F_Smith (edited May 28, 1999).]

[JimC]

Druid2: what's the problem?

Any specific error messages etc?

Jim

[Mark_Everson]

Jim:

Great Job. And your news about HotSpot is some of the best I've heard in a while. I only tried a few things with it this time. I have to force myself to write up the econ system now...

Cya, Mark

[Druid2]

Sorry.. that prev. msg wasnt very helpful was it...

I get a large grey box on black bkgrnd. Title at the top "Back to Homepage" link at the bottom, and nothing else.

The msg is:
Applet MapNodeApplet/MapNodeAPplet can't start: error: java.lang.ClassFormatError: MapNodeApplet/MapNodeApplet != MapNodeApplet

btw: I'm running Netscape Communic. 4.05 from Win95b on Pentium II

[This message has been edited by Druid2 (edited May 29, 1999).]

[JimC]

Maybe Netscape_4.05 isn't compatible with JDK1.2 - I've used Netscape_4.51 on a Unix box and it works.

Hmmmmmm....

Jim

[Blade Runner]

Netscape 4.05 or 4.06 compatible only Java 1.0.2 :-(
Netscape 5.0 will be compatible fully with Java 1.2 (They promis). I use Win95 OSR2 and Netscape 4.51 and everything is fine.

Blade Runner


[This message has been edited by Blade Runner (edited May 31, 1999).]