TheGameCreators - CodeBase - Heap storage example

Return to the CodeBase listing

Category: Miscellaneous

Version: 1.0

Information

Uploaded: 4th Sep 2003 14:02

Modified: 15th Sep 2003 08:16

Author: IanM

Summary

Example of the Heap system used in the A* pathfinding routine

Full Description

Heaps are a quick and easy way to organise data to allow you to retrieve that data in sequence without keeping the data completely sorted. You can find a description of how a heap is arranged and modified here : http://webpub.alleg.edu/student/g/groganb/heap_text.html There is a difference though ... I have reversed mine so that the lowest value is held at the top of the tree.

DarkBASIC Professional Source Code

` This code was downloaded from The Game Creators

` It is reproduced here with full permission

` http://www.thegamecreators.com

` Example of using a heap.

` This example just add items to the heap and then removes them.

` This also shows that heaps retain relative ordering (ie two items

`  with a sort value of 5 are added, and are removed in the same

`  sequence)

` You will find a version of the heap algorithm at the heart of my

` A* search code, ensuring that shortest paths are checked first.

type HeapStore

SortOrder as integer

StoredValue as integer

endtype

global dim Heap(0) as HeapStore

global HeapSize=0

Insert(10,0)

Insert( 5,1)

Insert(15,2)

Insert( 7,3)

Insert(43,4)

Insert( 1,5)

Insert( 5,6)

PrintHeap()

print "Additions done"

while not Empty()

print Heap(0).SortOrder; " - "; Heap(0).StoredValue

Delete()

endwhile

PrintHeap()

print "Deletion done"

wait key

end

function PrintHeap()

for i=0 to HeapSize-1

print Heap(i).SortOrder; " - "; Heap(i).StoredValue

next i

endfunction

function Insert(SortOrder as integer, StoredValue as integer)

local Parent as integer

local Child as integer

Child=HeapSize

inc HeapSize

if array count( Heap() ) <= Child then array insert at bottom Heap(), (HeapSize/2)+1

if Child <= 0 then exit

Parent=(Child - 1)/2

if Heap(Parent).SortOrder < SortOrder then exit

Heap(Child) = Heap(Parent)

Child = Parent

loop

Heap(Child).SortOrder = SortOrder

Heap(Child).StoredValue = StoredValue

endfunction

function Delete()

if HeapSize <= 0 then exitfunction

dec HeapSize

SortOrder=Heap(HeapSize).SortOrder

StoredValue=Heap(HeapSize).StoredValue

Parent=0

Child=(2 * Parent)+1

if Child >= HeapSize then exit

if Child+1 < HeapSize then if Heap(Child).SortOrder > Heap(Child+1).SortOrder then inc Child

if Heap(Child).SortOrder < SortOrder

Heap(Parent) = Heap(Child)

Parent = Child

else

exit

endif

loop

Heap(Parent).SortOrder = SortOrder

Heap(Parent).StoredValue = StoredValue

endfunction

function Empty()

if HeapSize <= 0 then exitfunction 1

endfunction 0

function Size()

exitfunction HeapSize

endfunction 0

Download

Please login to download

Comments

No comments yet.

Author Name:	IanM
CodeBase Entries:	26

CodeBase - Heap storage example

Information

Summary

Full Description

DarkBASIC Professional Source Code

Download

Screen Shot

Author

Comments