Array Allocation Management Examples
This example demonstrates a stack approach managing active & free objects within a array, without iterating through the object array looking for free spaces. It's works via storing all the available slots in the free stack and the allocated slots on the allocated stack. In this example I've used two arrays for clarity. Cell zero is used as the current stack size of either.
When a new objects is requested, we pop the last item from the free stack then add it to the allocated stack. To retrieve is a little trickier logically, but effectively all were doing is copying the last used item from the allocated stack over the cell being released. This freed index is then placed back on the free stack. This keeps the allocated stack sequential without having to copy the cells above the delete point down.
To process the 'active' objects we iterate through the allocated stack, starting at index 1 and ending size value held in cell zero of the allocation stack. . In this example the values stored in the stacks are indexes to whatever array you have to associate it with. This could be made into a generic manager if you wanted, but that's for you do to :)
Although, there is of course a simpler approach to doing this, which i'll demo in a minute.
Download Attached
Array Allocation Management - Sequential Allocation Via Last Cell Swapping
This example is variation of the above method. The object in there version is to keep our array of activate objects packed together within one array. So Active objects are stored from cell 1 to the number of objects. The containing array is never searched, or resized. You can easily add some code tro handle expanding the array if need be, but it's not included in this example.
When a new ball object is requested, we simply bump the BallCount variable (This is just a variable that holds the current number of used objects in our array) and return this as the new free index. To free a cell, we simply the swap the last cell with the cell we wish to remove. Then decrease the ball counter variable. The trick here is the swap. In order to swap the elements in the typed array we're simply peeking the address of the cell to the remove and the last cell and swapping the handles they contain. Hey presto...
To iterate through the list of active objects (balls in this examples case), we just run a for loop from the index 1 to BallCount. Obviously since we're possibly exchanging the order of cells while processing the list, it's assumed we're going to managing objects from start to finish. If a current object is deleted, then we need to step back and repeat this loop (at this for counter position) other wise the last object(s) in the list won't get refreshed if there's a prior deletion. Think about it :)
Download Attached
Array Allocation Management Examples (combined Example)
This example is a variation of the first stack method. In the first example we're using two arrays to manage free and allocated 'indexes' - However we can pack this into a single array.
As per the first example, we initialize our allocation array with the sequence of FREE indexes. Cell zero is used to keep track of the number of allocated Items. Initially, this cell is zero. (Since there's no allocated Items in the list, only free items)
To get a free Index , we query number of allocated items (get cell zero) and then return this INDEX at this position in the allocation array. In this example, it screens the number of items against the size of the allocation array. If the allocation count is maxed it, it doesn't bother returning anything. You could of course Expanded the array in these situations, but that's an exercise for the user .. :)
To delete items, we simply swap the cell to be deleted with the last allocated cell, then decrease the allocation count. If you think about it, the allocation count is conceptually a divider between the two halves of the array. On the left side (from index 1 to allocation count) we have allocated cells, on the right side (from the number allocated cells to the end of the array) we have the free cells. So we're really just moving the marker point.
To process the 'active' objects we iterate through the allocated stack array, starting at index 1 and ending size value held in cell zero of the allocation stack. .
[pbcode]
; PROJECT : Array_Allocation_Manager_Combined
; AUTHOR : Kevin Picone
; CREATED : 7/4/2008
; EDITED : 7/4/2008
; ---------------------------------------------------------------------
Type TObject
X,y
Size
Colour
EndType
// Array to store both free and Allocated object indexes in
Dim AllocatedStack(1)
// Typed array container to hold the actual objects
Dim Balls(1) as Tobject
// In the Allocated/Free Index arrays
InitAllocator(1000)
;*=-----------------------------------------------------------------------------=*
; >> Main Loop <<
;*=-----------------------------------------------------------------------------=*
Do
// Clear the Screen
Cls rgb(0,0,0)
// ====================================
// Randomly add a new objects to the scene
// ====================================
if timer()>AddNextObject
AddNextObject=timer()+rndRange(1,20)
// Get Free Object time
index=NewBall()
if Index
// Init the object at this position
balls(index).x# =-20
balls(index).y# =Rnd(600)
balls(index).size =RndRange(10,20)
balls(index).Colour =rndrgb()
endif
endif
// ====================================
// Process Allocated Object Stack
// ====================================
lockbuffer
AllocatedCount=AllocatedStack(0)
for lp=1 to AllocatedCount
Index=AllocatedStack(lp)
// Just make sure we're got an legal index (assume to be positive integer)
If Index
// Move ball right and draw it
Xpos=balls(index).x+1
Circlec xpos,balls(index).y,balls(index).Size,true,balls(index).Colour
balls(index).x=Xpos
// Check if ball is still on the screen
if xpos> 820
//If not, reclaim it....
// Null this pointer in the typed array
Balls(index)=null
// reclaim this index from the allocated list
AllocatedCount=ReclaimBall(lp)
// Step back to the current index, to avoid missing the last
// object, since they were swapped during reclaim (delete) process.
dec lp
endif
Endif
Next
UNlockbuffer
Size=GetArrayElements(AllocatedStack(),1)
print "Used Count:"+str$(AllocatedStack(0))
print "Free Count:"+str$(Size-AllocatedStack(0))
Sync
loop
;*=-----------------------------------------------------------------------------=*
; >> Init the Allocation Arrays <<
;*=-----------------------------------------------------------------------------=*
Function InitAllocator(Size)
Dim AllocatedStack(Size)
Dim Balls(size) as tobject
; predefine list of free cells from index 1 to array size
For lp=1 to Size
AllocatedStack(lp)=lp
Next
; set the number of allocated objects to zero
AllocatedStack(0)=0
EndFunction
;*=-----------------------------------------------------------------------------=*
; >> Allocate New Ball <<
;*=-----------------------------------------------------------------------------=*
Function NewBall()
//Stack Sizes are store in Index 0 of the array
UsedCount =AllocatedStack(0)+1
if UsedCount<=GetArrayElements(allocatedStack(),1)
index=AllocatedStack(USedCount)
AllocatedStack(0)=UsedCount
endif
EndFunction index
;*=-----------------------------------------------------------------------------=*
; >> Reclaim Ball <<
;*=-----------------------------------------------------------------------------=*
Function ReclaimBall(AllocatedIndex)
// Get the size of the Allocated Stack
UsedSize=AllocatedStack(0)
// Swap reclaimed object with the Last object in the allocated list
Index=AllocatedStack(AllocatedIndex)
AllocatedStack(AllocatedIndex)=AllocatedStack(UsedSize)
AllocatedStack(UsedSize)=Index
// Lower the allocated stack size
dec UsedSize
// store size back in header
AllocatedStack(0)=UsedSize
EndFunction UsedSize
[/pbcode]
Download Attached PlayBASIC Project