Map AI so far....

JimC · May 26, 1999, 20:27

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 · May 26, 1999, 20:50

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 · May 26, 1999, 21:08

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 · May 27, 1999, 03:32

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 · May 27, 1999, 07:25

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 · May 27, 1999, 23:13

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 · May 28, 1999, 00:32

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 · May 28, 1999, 14:28

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 · May 28, 1999, 15:47

Wish I could go and look at it

*pout*

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

F_Smith · May 28, 1999, 16:36

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 · May 28, 1999, 17:32

Druid2: what's the problem?

Any specific error messages etc?

Jim

Mark_Everson · May 28, 1999, 18:37

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 · May 29, 1999, 00:00

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 · May 29, 1999, 05:45

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 · May 29, 1999, 11:25

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

Druid2 · May 30, 1999, 15:15

Upgraded to Netscape 4.6 last nite, and now the applet runs fine.

I have no idea what it's doing, mind you.

But if it's supposed to put numbers in the map squares, it's running fine. *LOL*

Rebel · June 7, 1999, 07:34

Druid:

And here I thought I was the only one that was totally lost in the woods.

Rebel

But seriously, it looks like it is doing a great job of figuring the intensitys, at least i hope that is what it was doing.

BTW, am running 98,communicator 4.5, on an AMD K6/350 and the applet seems to run fine.
Just to let you know that it does run on other processors.

Rebel

Blade Runner · June 7, 1999, 16:07

Rebel,

I use AMD too (K6-II 300). I plant to change K-7 as soon as possibile. (IMHO the best processor of the century) ;-)

Blade Runner

Druid2 · June 9, 1999, 00:01

JimC,

[I cant get the app to run this morning, so I'm commenting on what I remember from the last time.]

As I remember it, the app goes on calculating the intensity value for each square, eventually, it will fill the entire displayed area until the goal is reached.

A) This suggestion involves some "pseudo-hueristic" pruning of the squares you need to calculate. "Pseudo" because in some cases, you will have to go back and re-activate the pruned branches.

After you've gone out n squares in each direction, you prune out the least desirable 50% of the squares. The you go about finishing the path calculation.

Only if the remaining paths lead to dead ends do you go back and calculate the already eliminated 50%.

Of course it wont be perfect; sometimes you'll wind up taking a "longer" path. But that would only be when the path goes in the "wrong" direction at first because there's a dramatic increase down there somewhere.

B) Also, I didnt try to look at the details of each loop, but this occurred to me as I was watching the numbers appear on the squares. If there are 3 squares [x(1), x(2), x(3)] , all of which could lead to square y, does the app calculate the value for each of the x(i)to y paths? or only for the most desirable of the x(i)?

Again, a compromise down from the "pure AI" maximized path, but a reasonable way of cutting down the number of iterations.

C) This one is more problematical, but might be a real time-saver if it can work. It is based on expanding particular paths, instead of calculating a value for a square. I cant explain it without an example [and maybe I cant explain it WITH an example

]:

The path is to be from X to Y, over some distance. X is roughly south of Y. Lets assume that a human would consider 3 paths: one heading NE from X and working back to Y, one heading N from X to Y, one heading NW from X and working back to Y.

As the app gets n squares out from X, you make the first path pruning. You identify the most desirable, 2nd most and 3d most desirable. I'll give them arbitrary values: [low value=more desirable]
1st = 2000, 2nd=3000, 3rd=4000 of "desirableness". {wrong term, but I want to purposely stay away from the ones you've used, in case I use them wrong.}

The concept is that there is now no reason to consider expanding any path except the 1st, until the value for path1 exceeds 3000 [the path2 value], then you need to expand them both. If either exceeds 4000 [path 3 value], you go back to expanding only one, until they are all over 4000.

Then you go back and get the path4 [path 4=5000, for example]. you continue expanding path 1,2 & 3 until one of them exceeds 5000.

At that point you continue to expand the paths until ALL of them are over the path4 value, or you get to the objective, etc etc.

[This is, to the degree I remember it, a swipe of some thing I saw in trying to do the "Knights Tour" on a chessboard.]

[This message has been edited by Druid2 (edited June 08, 1999).]

Mark_Everson · June 9, 1999, 00:10

Druid:

I think you need to read the description in the link in my first post in this thread to know what's going on. This intensity thing is using multiple paths spanning different parts of the map to find the strategic spots like isthmuses (You know, the ones people block off in civ, but the AI has No clue about). The path intensity calculation will be run in the background, so it won't slow the game down. Doing this work in the background should actually make unit pathfinding easier and quicker.

Druid2 · June 9, 1999, 00:17

Mark,

Aw *CHIT*

I said all along, I didnt grok the intensity thing.. *LOL* at myself.

But if this is in background, and available when the moves are being determined, then I dont understand the 'tileless' movement problems...

Communication by forum post is NOT the best way.. *L*

JimC · June 17, 1999, 09:42

bump....

Just in case anyone wonders where I've been - I'm working on a Genetic Programming package that may be of some use to this project.... who knows.

Jim

Mark_Everson · June 17, 1999, 21:17

Hey Jim:

I was wondering, but hey, people have Lives and stuff

. I'd certainly like to see your package when its ready.

-Mark

JimC · June 18, 1999, 05:43

It's pretty much finished, but I'm doing some extensive modifications to prevent the computer 'cheating'

examples - multiplying a subtree by -1 twice, then claiming that it's a good mutation because a high fitness value has been maintained

or - 'fudging' the integer value 0 by taking the sin of a random value about 10 times

or - mutating a value which has been multiplied by 0 and claiming it as a valid mutation

etc. etc....

It doesn't seem to like running under the Hotspot JIT for some reason - I've sent a bug report to JavaSoft and it will hopefully be sorted out in the next release.

That's all for now.

Jim