- This topic has 24 replies, 9 voices, and was last updated 17 years, 11 months ago by
.
-
Posts
-
-
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 -
I like kittens.
-
I like kittens. [/quote:471ae0b921]
why, why would you say that man..
they pee and crap everywhere?
-
Sorry Peter, I didnt understand your post so I’d thought I’d be silly.
*uses psychic energy to get thread back on track*
-
heh, we need a separate technical section here, the creatives are starting to lose it ;)
-
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”. :)
-
A copy would be great.
-
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?
-
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…
-
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,
-
Oh god how i hated the path finding algorithms assignment…:mad:
-
ah there not so bad. key is alway draw a diagram, and think in simplistic terms :)
-
*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!
-
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. -
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…. -
*innocently walks into thread whistling merrily*
*everyone stops, and stares*
*walks straight back out again*
[/quote:baafe378d4]
-
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.
-
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.
-
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.