[bb] Project PLASMA FPS 2004: Queue.bb by Techlord [ 1+ years ago ]

[BlitzBot]

Title : Project PLASMA FPS 2004: Queue.bb
Author : Techlord
Posted : 1+ years ago

Description : Binary Heap Priority Queue that sorts by lowest key integer value. Used in Bot.bb Pathfinding algo. Can be used for other operations that require sort by priority.

<div class="quote"> Summary of functions:

queueCreate(size%) Creates a queue of a specified size. Size should not exceed QUEUEITEM_MAX%.

queueDestroy(this.queue) Removes a queue and all of its items from memory.

queuePush(this.queue,key%,dat%) Inserts and sorts a item data value by key value.

queuePop(this.queue) Extracts the first data value and resorts by key value.
</div>

Requires: <a href="codearcsd8c0.html?code=889" target="_blank">Stack.bb[/url]

Last Update 01/16/04
Check out the <a href="http://techlord.blackeve.com/ppf2k4.zip" target="_blank">Wip Zip[/url] for demos and more code!

Code :

Code: BlitzBasic

1. ;Priority Queue - Binary Heap Sort by Lowest Key
2. ;modified by Frankie 'Techlord' Taylor
3.  
4. ;References  
5. ;http://www.policyalmanac.org/games/binaryHeaps.htm
6. ;http://www.developersdomain.com/vb/articles/queue.htm
7.  
8. ;============================
9. ;QUEUEITEM
10. ;============================
11.  
12. Const QUEUEITEM_MAX=4096
13. Dim queueitemIndex.queueitem(QUEUEITEM_MAX)
14.  
15. Type queueitem
16.         Field id%
17.         Field key%
18.         Field dat%
19. End Type
20.  
21. Function queueitemStop()
22.         For this.queueitem=Each queueitem
23.                 queueitemDelete(this)
24.         Next
25. End Function
26.  
27. Function queueitemNew.queueitem()
28.         this.queueitem=New queueitem
29.         thisid%=0
30.         thiskey%=0
31.         thisdat%=0
32.         Return this
33. End Function
34.  
35. Function queueitemDelete(this.queueitem)
36.         Delete this
37. End Function
38.  
39. Function queueitemMimic(mimic.queueitem,this.queueitem)
40.         mimicid%=thisid%
41.         mimickey%=thiskey%
42.         mimicdat%=thisdat%
43. End Function
44.  
45. Function queueitemCreate.queueitem(id%=0,key%=0,dat%=0)
46.         this.queueitem=queueitemNew()
47.         thisid%=id%
48.         thiskey%=key%
49.         thisdat%=dat%
50.         Return this
51. End Function
52.  
53. Function queueitemSwap(queueitem1.queueitem,queueitem2.queueitem)
54.         queueitemkey%=queueitem1key%
55.         queueitemdat%=queueitem1dat%
56.         queueitem1key%=queueitem2key%
57.         queueitem1dat%=queueitem2dat%
58.         queueitem2key%=queueitemkey%
59.         queueitem2dat%=queueitemdat%
60. End Function
61.  
62. ;============================
63. ;QUEUE
64. ;============================
65. Const QUEUE_MAX=255
66. Dim queueId.queue(QUEUE_MAX)
67. Global queueIndex.stack=stackIndexCreate(QUEUE_MAX)
68. Global queueAvail.stack=stackIndexCreate(QUEUE_MAX)
69.  
70. Type queue
71.         Field id%
72.         Field size%
73.         Field queueitems%
74.         Field queueitem.queueitem[QUEUEITEM_MAX]
75. End Type
76.  
77. Function queueStart(n=2)
78.         For loop = 1 To n%
79.                 queueCreate()
80.         Next
81.         DebugLog "Queues Initialized ["+Str(n)+"]"     
82. End Function
83.  
84. Function queueStop()
85.         For this.queue=Each queue
86.                 queueDelete(this)
87.         Next
88. End Function
89.  
90. Function queueNew.queue()
91.         this.queue=New queue
92.         thisid%=0
93.         thissize%=0
94.         thisqueueitems%=0
95.         thisid%=StackPop(queueIndex.stack)
96.         queueId(thisid)=this
97.         Return this
98. End Function
99.  
100. Function queueDelete(this.queue)
101.         queueId(thisid)=Null
102.         StackPush(queueIndex.stack,thisid%)
103.         Delete this
104. End Function
105.  
106. Function queueCreate.queue(size%=QUEUEITEM_MAX)
107.         this.queue=queueNew()
108.         thisqueueitems%=0
109.         thissize%=size%
110.         For loop=0 To thissize%
111.                 thisqueueitem.queueitem[loop]=queueitemCreate()
112.         Next
113.         Return this
114. End Function
115.  
116. Function queueDestroy(this.queue)
117.         For loop=0 To thissize%
118.                 queueitemDelete(thisqueueitem[loop])
119.         Next
120.         thisqueueitems%=0
121.         queueDelete(this)
122. End Function
123.  
124. Function queuePush(this.queue,key%,dat%)
125.     thisqueueitems%=thisqueueitems%+1
126.     thisqueueitem[thisqueueitems%]key%=key%
127.     thisqueueitem[thisqueueitems%]dat%=dat%
128.         queueBuild(this,thisqueueitems%)       
129. End Function
130.  
131. Function queuePop(this.queue)
132.     If thisqueueitems%
133.                 dat%=thisqueueitem[1]dat%
134.                 queueitemMimic(thisqueueitem[1],thisqueueitem[thisqueueitems%])
135.                 thisqueueitems%=thisqueueitems%-1
136.         queueRebuild(this,1)
137.                 Return dat%
138.     EndIf
139. End Function
140.  
141. Function queueBuild(this.queue,queuechild%)
142.     queueparent%=queuechild%/2
143.     If thisqueueitem[queuechild%]key%<thisqueueitem[queueparent%]key%
144.                 queueitemSwap(thisqueueitem[queuechild%],thisqueueitem[queueparent%])
145.         queueBuild(this,queueparent%)
146.     EndIf
147. End Function
148.  
149. Function queueRebuild(this.queue,queueparent%)
150.     queuechild%=2*queueparent%
151.         queuechild2%=queuechild%+1
152.     If queuechild%<thisqueueitems%
153.         If thisqueueitem[queuechild2%]key%<thisqueueitem[queuechild%]key% queuechild%=queuechild2%
154.         If thisqueueitem[queuechild%]key%<thisqueueitem[queueparent%]key%
155.                         queueitemSwap(thisqueueitem[queueparent%],thisqueueitem[queuechild%])
156.             queueRebuild(this,queuechild%)
157.         End If
158.     End If
159. End Function
160.  
161. Function queueDump(this.queue)
162.         For loop = 1 To thissize%
163.                 value%=queuePop(this)
164.                 If value% DebugLog value%
165.         Next
166. End Function
167.  
168. Function queuePushLargest(this.queue,key%,dat%)
169.     thisqueueitems%=thisqueueitems%+1
170.     thisqueueitem[thisqueueitems%]key%=key%
171.     thisqueueitem[thisqueueitems%]dat%=dat%
172.         queueBuildLargest(this,thisqueueitems%)
173. End Function
174.  
175. Function queuePopLargest(this.queue)
176.     If thisqueueitems%
177.                 dat%=thisqueueitem[1]dat%
178.                 queueitemMimic(thisqueueitem[1],thisqueueitem[thisqueueitems%])
179.                 thisqueueitems%=thisqueueitems%-1
180.         queueRebuildLargest(this,1)
181.                 Return dat%
182.     EndIf
183. End Function
184.  
185. Function queueBuildLargest(this.queue,queuechild%)
186.     queueparent%=queuechild%/2
187.     If thisqueueitem[queuechild%]key%>thisqueueitem[queueparent%]key%
188.                 queueitemSwap(thisqueueitem[queuechild%],thisqueueitem[queueparent%])
189.         queueBuildLargest(this,queueparent%)
190.     EndIf
191. End Function
192.  
193. Function queueRebuildLargest(this.queue,queueparent%)
194.     queuechild%=2*queueparent%
195.         queuechild2%=queuechild%+1
196.     If queuechild%<thisqueueitems%
197.         If thisqueueitem[queuechild2%]key%>thisqueueitem[queuechild%]key% queuechild%=queuechild2%
198.         If thisqueueitem[queuechild%]key%>thisqueueitem[queueparent%]key%
199.                         queueitemSwap(thisqueueitem[queueparent%],thisqueueitem[queuechild%])
200.             queueRebuildLargest(this,queuechild%)
201.         End If
202.     End If
203. End Function
204.  
205. Function queuePopLast(this.queue)
206.     If thisqueueitems%
207.                 dat%=thisqueueitem[thisqueueitems%]dat%
208.                 thisqueueitems%=thisqueueitems%-1
209.     EndIf
210.         Return dat%
211. End Function

Comments : none...