Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Code Snippets / YAA*AI (Yet Another A* Algorithm Implementation)

Author
Message
Owl
21
Years of Service
User Offline
Joined: 28th Sep 2003
Location: Imatra, Finland
Posted: 2nd Oct 2003 16:35
Link
Okay, I just have to get attention: I know there's been some threads about this, and also that there is (at least should be) snippets in the codebase regarding A* and other pathfinding algorithms, but I just had to figure this on my own. For some odd reason. And now that I've done it, I need some publicity, otherwise it would've been coded for nothing.

...and I thought I'd also ask at the same that if people could go over this and give feedback (how to improve, bugs, etc...).

I know about some already, but it's in enough working condition to say that it works. 8-D

I believe that most of the overhead in that is basically the "live observation"...

Here are some media files for it (1bpp bitmaps representing maps)
http://corrie.scp.fi/users/jani.karkkainen/m100x100.bmp
http://corrie.scp.fi/users/jani.karkkainen/m8x8.bmp
Back to top
Profile PM Email
Owl
21
Years of Service
User Offline
Joined: 28th Sep 2003
Location: Imatra, Finland
Posted: 2nd Oct 2003 19:09
Link
Agh. HUGE Bug(tm). A little bit of thinking and some more reading on the subject, I believe it is now bugless (hah! ). Here's the new code.
Back to top
Profile PM Email
Owl
21
Years of Service
User Offline
Joined: 28th Sep 2003
Location: Imatra, Finland
Posted: 2nd Oct 2003 19:27
Link
Umm. Damn.

Third time is the ticket. This time I won't put the whole code, it seems too wasteful.. so, on line 125:

if (estimate < curnode.cost + curnode.heuristic)

change that to

if (estimate < a_list(closed, inclosed).cost + a_list(closed, inclosed).heuristic)

and NOW it should work correctly. If it doens't, I'll curl up and die.
Back to top
Profile PM Email
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 2nd Oct 2003 21:44
Link
It works ... if you change the mapwidth/mapheight variables to match your bitmap size

Nice one!
Back to top
Profile PM Email Website
ReD_eYe
21
Years of Service
User Offline
Joined: 9th Mar 2003
Location: United Kingdom
Posted: 2nd Oct 2003 21:59 Edited at: 2nd Oct 2003 22:02
Link
hehe, i had to wait abit but it works good!


Back to top
Profile PM Email Website
Owl
21
Years of Service
User Offline
Joined: 28th Sep 2003
Location: Imatra, Finland
Posted: 3rd Oct 2003 18:20
Link
Oh yes, I noticed that too... I'll be fiddling with it a bit for a while, and probably tidy the code and stuff, before I incorporate it into my game... I think it would be way faster if I discarded the drawing of the map and progress and so on. I'm not gonna test that yet though, because it's fun to watch that thing go!

Thanks for the input, gives me more motivation to continue to code!
Back to top
Profile PM Email
Back to top

Login to post a reply

Server time is: 2024-11-24 01:36:27
Your offset time is: 2024-11-24 01:36:27