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 / [DBP] Binary Heaps Using Memory Banks (needs Matrix1Utils)

Author
Message
Aurum Knight
15
Years of Service
User Offline
Joined: 15th Jul 2008
Location: the suburbs of nowhere
Posted: 2nd Aug 2010 20:23
I made this for an A* thing I've finally got working, so I thought I'd share this with everyone.

Binary heaps are a very fast way to sort things if the only part you need to be sorted is the item with the lowest value (or highest).

Here's the tutorial I learned the concept from: (link)

Here's the code:


What I store in the 'tag' is an index to an array (which has more data). If you ever want to lower a value, you have to resort it using the function 'bhResort'. Use the function 'bhFindTag' to find an index with a particular tag.

'Resort' doesn't work if you raise the value of an index (this was made with A* in mind) If anyone cares to have a version of this that works the other way (the option of putting the highest value at the top), feel free to ask me to do it. This can be really confusing to edit since it uses memory banks.

It probably wouldn't be too hard to change this to use with memblocks fyi.

Enjoy.
IanM
Retired Moderator
21
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 11th Aug 2010 21:35
Quote: "Here's the tutorial I learned the concept from:"

Me too, although I've used other sources since then too.

My own grid-based A* code uses a binary heap, which I separated out of the code and posted on it's own in the codebase

Aurum Knight
15
Years of Service
User Offline
Joined: 15th Jul 2008
Location: the suburbs of nowhere
Posted: 13th Aug 2010 03:09
I haven't actually tried your (or anyone else's) A*, so I don't know how fast (or slow) mine is comparatively, much less with the binary heap. My guess is yours is much faster The only reason I used banks was because I thought I may need multiple heaps saved if I want to spread the path finding code over several loops so that it doesn't freeze up whenever you move a unit. It would've been much easier to just do it the normal way.

Like I said, I have a basic grid based A* working. Once I get my coding computer working again I was going to look into using navigation meshes. They'll probably work better, but they may be a bit of a challenge.

Maybe there's some A* discussion thread I should have posted this in...

Login to post a reply

Server time is: 2024-03-28 15:48:57
Your offset time is: 2024-03-28 15:48:57