How to Boost A* by 40-50%

I like kittens. [/quote:471ae0b921]

why, why would you say that man..

they pee and crap everywhere?

ah right.

basically A* which im sure you know does path finding in practically every game for the last 5-6 years possible longer. its a good algorithm but unless highly optimised it could really bottleneck your game.
so this method basically implements a version of a* which is easy to program but is highly optimised (algorithmly), instead of programming specific shortcut, which claims to improve by 40% percent or so.
i have yet to implement myself but when i get a chance ill let ye know. i do know the guys from the game companies who were there were pretty impressed, scribbling like notes like made and asking questions, which you knew were specifically aimed towards their next games or own purpose. one guy from codemasters i think, told me he was going into work tomorrow and changing their implementation to see if he could get more out of his ai.

heh, we need a separate technical section here, the creatives are starting to lose it ;) [/quote:f23ea8c867]

hehe,

ya we can call it “talking techno shop”. :)

anyone know the copyright issues with ieee publications, will i get my ass sued off me, steph?? if i scan it and send it to a few of the lads?

At any rate, isn’t IEEE a ‘public’ body, e.g. publishing proceedings and papers free? Or do you have to be a (paying?) member to access stuff?

[/quote:ca34b04b07]

ieee isnt free, its quite expensive to join, fairly limited also. I remember after graduating i tried to join and they said cs in u.c.c. wasent ieee approved, i think the only cs course at the time was tcd computer eng i think(if theirs such a thing). although they did say if i worked for a year or so in the field of research in some specific area and got published by them i could join. so maybe ill try again, might even get the student rate.

as for the paper, im going to send the author an email and see if he’ll give me the pdf and permission to spread,

ah there not so bad. key is alway draw a diagram, and think in simplistic terms :)

yeah fair enough, enough on the tech side.
if i manage to get that paper ill send on, i emailed the author so waiting to hear back.

well spent most of today implementing this fringe search and gotta say when people write pseudo in a paper they really should get somone who knows nothing about the paper to code it up by just reading the paper and coding, so that all nooks and crannys are spotted.

i found a few small mistakes in the pseudo code which required a good few reads of the paper to spot and fix, i.e. things mislabelled resulting in drastic effects).

anyway after a day of reading\coding\reading coding\correcting\running. I final got the thing to work. dunno if its much faster than a* i might run it against a ME_IDA* (which this things claims it can beat, we’ll see ;-) ), next week.

Anyway, so ill clean up the code and post on my website next week if someone wants to integrated it into a project.
when im done it should read a standard text file, parse it build a map, person supplies start and end points. hopefully, voila and out pops your path to move your troops etc.

but ill supply the source also, so you can integrate however you like.

also the conference guy told me the paper will be available in about a week. i went to scan the algorithm at work but as usual busted.

from here.
http://cscourse.essex.ac.uk/cig/

right that ends the topic (probably too much techno talk).

home bound!

well like promised heres the code for this algorithm.(if anyone wants it).

its pretty clean i think, not highly optimised, (i use stl vectors, so i suggest if anyone is to use it, convert these to arrays). Probably a few more optimisation could be made.

Also i threw in a sample map, but no doubt anyone who uses it will have their own map format, so it should be easy to change to plugin in theirs.

heres the link, its on the top of the page.

http://student.cs.ucc.ie/~pb2/work.html

peter

p.s. ill try to post a map builder soon, which automates the creation of these maps.

site is now updated with a simple map builder to use with the algorithm. (its an early release but should be stable enough, not much time to test the thing)

although at the moment the maps generated are in a different file format to the one used in the algorithm zip. i will change this tomorrow and repost a zip file which has the changes made.

peter

all updates are now done to the map builder, it now produces maps which can be directly feed into the search executable. so if you happened to download it to give it a whizz (re-download both) to make sure you have latest version.

anyway hope its useful.

peter

Map builder needs

http://www.excelsior-usa.com/jetdlevala.html

installed it seems. [/quote:a105d22535]

ya sorry about that, i thought excelsior would allow me to create an .exe which was eliminated need for jre, i think thats only available in professional edition.

Java version up now.

This games conferences proceedings are all online now, so you can read about this fringe search and many more cutting edge ai techniques which were presented.

http://csapps.essex.ac.uk/cig/2005/index.jsp?page=papers.html