Home › Forums › Programming › How to Boost A* by 40-50%
- This topic has 24 replies, 9 voices, and was last updated 17 years, 11 months ago by
Anonymous.
-
AuthorPosts
-
-
April 13, 2005 at 11:40 am #3994
Anonymous
Inactivei was recently at this games ai conference and a guy from alberta gave a talk on the algorithm which he called fringe IDA* (iterative deepening A*), typically IDA* is used to do a* pathfinding with lower overhead, because of the way you visit and store node. its going to be published on IEEE website i guess in the next couple of months, (i got a copy in the proceedings), if anyone is interested in the paper give me a shout and i can photo-copy and send on or perhaps scan. i reckon it could really help ai developers to get an extra ounce out of there cpu cycles.
anyway basic addition he made was an observation about the fringe nodes(nodes visited last before the deepening ended), essentially he stores these so he could resume from them if A* deemed them promising in the future. Thus saving reduces the recalculation of path to these nodes, and saves valuable “memory”.
heres the name of the paper and the authors, incase any of ye can find it on google. i couldnt though.
Fringe Search: Beating A* at Pathfinding on Game Maps
Authors:
Yngvi Bjornsson, Markus Enzenberger, Robert Holte and Jonathan Schaeffer -
April 13, 2005 at 4:36 pm #19897
Anonymous
InactiveI like kittens.
-
April 13, 2005 at 4:40 pm #19898
Anonymous
InactiveI like kittens. [/quote:471ae0b921]
why, why would you say that man..
they pee and crap everywhere?
-
April 13, 2005 at 4:43 pm #19900
Anonymous
InactiveSorry Peter, I didnt understand your post so I’d thought I’d be silly.
*uses psychic energy to get thread back on track*
-
April 13, 2005 at 4:48 pm #19903
Anonymous
Inactiveheh, we need a separate technical section here, the creatives are starting to lose it ;)
-
April 13, 2005 at 4:50 pm #19904
Anonymous
Inactiveah 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. -
April 13, 2005 at 4:52 pm #19905
Anonymous
Inactiveheh, 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”. :)
-
April 13, 2005 at 4:54 pm #19906
Anonymous
InactiveA copy would be great.
-
April 13, 2005 at 4:57 pm #19907
Anonymous
Inactiveanyone 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?
-
April 14, 2005 at 7:31 am #19925
Anonymous
InactiveDepends if there’s any explicit mentions on the material not to do so, e.g. marked “confidential”, “not for (public) release”, etc.
And whether the speaker has explicitly stated (orally) that he intended for his presentation and hand-out to be priviledged/confidential/not for release/etc.If so, then no you can’t. If not, then there shouldn’t be any problem. But the answer probably lies in the middle, however I’ll need more info to precise that :)
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?
Under copyright Statutes, you should always obtain consent of the author. But who’s the author? The lecturer/presenter or the IEEE? Just have a close look at the material handed out, I’d be very surprised if there isn’t a copyright mention somewhere and font-size-1 ‘rules & regs’ regarding the reproduction and distribution of this paper. Let me know…
-
April 14, 2005 at 9:26 am #19945
Anonymous
InactiveAt 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,
-
April 14, 2005 at 3:32 pm #20015
Anonymous
InactiveOh god how i hated the path finding algorithms assignment…:mad:
-
April 14, 2005 at 3:35 pm #20016
Anonymous
Inactiveah there not so bad. key is alway draw a diagram, and think in simplistic terms :)
-
April 14, 2005 at 3:45 pm #20020
Anonymous
Inactive*innocently walks into thread whistling merrily*
*everyone stops, and stares*
*walks straight back out again*
All this AI stuff is going way over my head!
-
April 14, 2005 at 3:48 pm #20021
Anonymous
Inactiveyeah 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. -
April 14, 2005 at 3:50 pm #20022
Anonymous
InactiveI’m not saying you should stop talking about it!!
It is certainly interesting, even if I can’t make sense of most of it…..but thats just me and my non-programming mind…. -
April 14, 2005 at 3:50 pm #20023
Anonymous
Inactive*innocently walks into thread whistling merrily*
*everyone stops, and stares*
*walks straight back out again*
[/quote:baafe378d4]
-
April 15, 2005 at 6:51 pm #20080
Anonymous
Inactivewell 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!
-
April 18, 2005 at 10:33 am #20090
Anonymous
Inactivewell 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.
-
April 18, 2005 at 4:36 pm #20118
Anonymous
Inactivesite 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
-
April 19, 2005 at 2:39 pm #20152
Anonymous
Inactiveall 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
-
April 19, 2005 at 2:50 pm #20155
Anonymous
Inactive -
April 19, 2005 at 2:59 pm #20156
Anonymous
InactiveMap 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.
-
May 15, 2005 at 9:00 pm #21207
Aphra K
Keymasterbit late on this one but usually as long as the original author is referenced and the details of the proceedings given you can freely quote.
You can also photocopy within current copyright limitations (these limits are usually posted up by the photocopiers in every university!) to circulate for educational and not for profit purposes..
there are some grey areas in there but just remember to quote the source..
Aphra.
-
July 7, 2005 at 4:16 pm #22874
Anonymous
InactiveThis 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
-
-
AuthorPosts
- The forum ‘Programming’ is closed to new topics and replies.