 |
| |
|
|
JimC
|
|
Birmingham, England
May 1999
time: 05:13
|
|
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
|
 |
Canton, MI
Jan 1970
time: 00:13
|
|
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
|
|
Austin, Tx, USA
May 1999
time: 05:13
|
|
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.
|
|
| |
|
|
|
JimC
|
|
Birmingham, England
May 1999
time: 05:13
|
|
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.
|
|
| |
|
|
|
JimC
|
|
Birmingham, England
May 1999
time: 05:13
|
|
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
|
|
| |
|
|
|
F_Smith
|
|
Austin, Tx 78728
May 1999
time: 05:13
|
|
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
|
|
Birmingham, England
May 1999
time: 05:13
|
|
Druid2: what's the problem?
Any specific error messages etc?
Jim
|
|
| |
|
|
|
Druid2
|
|
Dallas,TX
May 1999
time: 05:13
|
|
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
|
|
Birmingham, England
May 1999
time: 05:13
|
|
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
|
|
| |
|
|
|
Druid2
|
|
Dallas,TX
May 1999
time: 05:13
|
|
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
|
|
Athens Ohio, USA
May 1999
time: 05:13
|
|
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
|
|
| |
|
|
|
Druid2
|
|
Dallas,TX
May 1999
time: 05:13
|
|
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).]
|
|
| |
|
|
|
Druid2
|
|
Dallas,TX
May 1999
time: 05:13
|
|
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
|
|
Birmingham, England
May 1999
time: 05:13
|
|
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
|
|
| |
|
|
|
JimC
|
|
Birmingham, England
May 1999
time: 05:13
|
|
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
|
|
| |
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
|
|
|
|
|
|
27-05-1999 05:27
*pout* 
|