Home Forums Programming How to Boost A* by 40-50%

Welcome to our forums. These forums were active from 2003-2014. We have now decided to close them down, but will leave them here as an archive.

Remember you can send us feedback, news, jobs and content ideas by clicking here.

If you're really stuck for time, email news@gamedevelopers.ie.

You can also follow us on Twitter @gamedev_ie 

 

 

This topic contains 24 replies, has 9 voices, and was last updated by  peter_b 12 years, 2 months ago.

  • Author
    Posts
  • #3994

    peter_b
    Participant

    i 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

  • #19897

    kyotokid
    Keymaster

    I like kittens.

  • #19898

    peter_b
    Participant

    I like kittens. [/quote:471ae0b921]

    why, why would you say that man..

    they pee and crap everywhere?

  • #19900

    kyotokid
    Keymaster

    Sorry Peter, I didnt understand your post so I’d thought I’d be silly.

    *uses psychic energy to get thread back on track*

  • #19903

    mal
    Participant

    heh, we need a separate technical section here, the creatives are starting to lose it ;)

  • #19904

    peter_b
    Participant

    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.

  • #19905

    peter_b
    Participant

    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”. :)

  • #19906

    RonanHayes
    Participant

    A copy would be great.

  • #19907

    peter_b
    Participant

    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?

  • #19925

    Steph
    Participant

    Depends 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…

  • #19945

    peter_b
    Participant

    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,

  • #20015

    gizmo
    Participant

    Oh god how i hated the path finding algorithms assignment…:mad:

  • #20016

    peter_b
    Participant

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

  • #20020

    Nooptical
    Participant

    *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!

  • #20021

    peter_b
    Participant

    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.

  • #20022

    Nooptical
    Participant

    I’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….

  • #20023

    kyotokid
    Keymaster

    *innocently walks into thread whistling merrily*

    *everyone stops, and stares*

    *walks straight back out again*

    [/quote:baafe378d4]

  • #20080

    peter_b
    Participant

    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!

  • #20090

    peter_b
    Participant

    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.

  • #20118

    peter_b
    Participant

    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

  • #20152

    peter_b
    Participant

    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

  • #20155

    Skyclad
    Participant

    Map builder needs

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

    installed it seems.

  • #20156

    peter_b
    Participant

    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.

  • #21207

    aphra
    Keymaster

    bit 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.

  • #22874

    peter_b
    Participant

    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

The forum ‘Programming’ is closed to new topics and replies.