Ooops
March 01, 2021, 10:45:33 PM

Author Topic: [bb] Project PLASMA FPS 2004: Queue.bb by Techlord [ 1+ years ago ]  (Read 548 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
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...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal