Hi,
I realized that not only
Tree Structures were missing in DBP but also a convenient way to handle a "Free List".
Take an array of units for a shooter game for example, most of them being AI-controlled. Some AI-Units may have an attack-target, which is a reference to another unit. Now imagine that a unit is killed - there are two ways to handle this event:
1. You can remove the unit from the unit-array - this has the striking disadvantage that the ID of all units that came after this one will now have a reduced array-position. Consequently you'd have to update all unit-references to avoid cases where the death of one unit results in most AI-units suddenly having another target.
2. You can use a boolean "exist"-flag for each unit which determines whether the unit is alive. If a unit dies, you simply set Unit(ID).exist = 0. This way the unit IDs stay the same when a unit dies, but there is another disadvantage: Either the unit array keeps growing and growing because every dead unit keeps its array element, or you actively search for those death units to overwrite them when creating a new one, which is in my opinion the best solution. But then again, there's much overhead because when the array gets big you may have to search for quite a while (only to realize that there is no dead unit in the worst case, so the whole search was pointless and a new element has to be created).
This problem is solved by a free list: There's a second array keeping hold of all the array-IDs of all dead units. When a new unit has to be created you simply pick an arbitrary array ID from the free list and use it as new unit ID.
Implementing such free lists individually when you need them is not all that hard, but can still be made easier by using a central system that manages several free lists at once. And this is, finally, where the library below comes in.
The commands available:
Quote: "
fl_init() - should be called once after starting your program
listID = fl_newList() - sets up a new list and returns the lists ID
fl_register(listID, index) - adds a value to the given Free-List, this value is usually an index of the array the list is responsible for
index = fl_revive(listID) - if the given Free-List still contains registered elements, it will return one of the indices you registered earlier; otherwise it returns -1.
string = fl_toString(listID) - converts the content of a free List into a string - can be used for debugging purposes
"
Here's the code for the library itself:
remstart
Code by MrKohlenstoff
V 0.1, 21th February 2012
Use or alter it however you want - if you name me
in the credits section of your project, I'll certainly
feel honoured. :)
remend
#constant fl_ITEMSTEP = 1024
function fl_init()
rem List Array
global fl_listCount as integer = 0
dim fl_List(0) as fl_ListType
rem Item Array
global fl_capacity as integer = fl_ITEMSTEP
global fl_count as integer = 0
dim fl_item(fl_capacity) as fl_ItemType
endfunction
type fl_ListType
firstItem as integer
lastItem as integer
items as integer
endtype
type fl_ItemType
list as integer
key as integer
prev as integer
nxt as integer
endtype
function fl_newList()
ID = fl__newList()
fl_List(ID).lastItem = 0
i = fl_register(ID,0)
fl_List(ID).firstItem = i
fl_List(ID).items = 0
endfunction ID
function fl_register(list,key)
ID = fl__newItem()
fl_item(ID).key = key
fl_item(ID).prev = fl_list(list).lastItem
fl_item(fl_list(list).lastItem).nxt = ID
fl_item(ID).nxt = 0
fl_item(ID).list = list
inc fl_list(list).items
fl_list(list).lastItem = ID
endfunction ID
function fl_revive(list)
if fl_List(list).items > 0
last = fl_List(list).lastItem
ID = fl_Item( last ).key
fl_List(list).lastItem = fl_Item(last).prev
fl_Item( fl_Item(last).prev ).nxt = 0
dec fl_list(list).items
rem Make sure there's no empty spot in the free list
if last < fl_count
fl__move(fl_count, last)
endif
dec fl_count
else
ID = -1
endif
endfunction ID
function fl_toString(list)
s$ = fl__toString( fl_Item( fl_List(list).firstItem ).nxt )
endfunction s$
function fl__toString(item)
if item = 0
s$ = ""
else
s$ = str$(fl_item(item).key) + " " + fl__toString( fl_item(item).nxt )
endif
endfunction s$
function fl__newList()
inc fl_ListCount
array insert at bottom fl_List()
ID = fl_ListCount
endfunction ID
function fl__newItem()
inc fl_count
ID = fl_count
if fl_count > fl_capacity
inc fl_capacity, fl_ITEMSTEP
array insert at bottom fl_item(), fl_ITEMSTEP
endif
endfunction ID
function fl__move(src,trg)
list = fl_item(src).list
fl_item(trg).list = list
fl_item(trg).key = fl_item(src).key
fl_item(trg).prev = fl_item(src).prev
fl_item(trg).nxt = fl_item(src).nxt
fl_item( fl_item(src).prev ).nxt = trg
fl_item( fl_item(src).nxt ).prev = trg
if fl_list( list ).lastItem = src
fl_list( list ).lastItem = trg
endif
if fl_list( list ).firstItem = src
fl_list( list ).firstItem = trg
endif
endfunction
And here's the code together with a usage example:
remstart
Code by MrKohlenstoff
V 0.1, 21th February 2012
Use or alter it however you want - if you name me
in the credits section of your project, I'll certainly
feel honoured. :)
remend
set display mode 800,600,32
sync on
sync rate 0
fl_init()
dim ListA(10) as boolean
dim ListB(10) as boolean
for i = 1 to 10 : ListA(i) = 1 : ListB(i) = 1 : next i
FreeA = fl_newList()
FreeB = fl_newList()
do
cls
x1 = 100
x2 = 300
rem Element List
ink 0xFFFFFFFF,0
center text x1, 50, "List A:"
center text x2, 50, "List B:"
for i = 1 to 10
y1 = 50 + 30*i
b1 = DrawBox(x1-15,y1,x1+15,y1+25,ListA(i))
b2 = DrawBox(x2-15,y1,x2+15,y1+25,ListB(i))
if b1 or b2 then waitForMouse = 1
if b1 and ListA(i)=1 then ListA(i)=0 : fl_register(FreeA,i)
if b2 and ListB(i)=1 then ListB(i)=0 : fl_register(FreeB,i)
next i
rem Free List
ink 0xA0FFFFFF,0
center text x1, 450, "Free Items: " + fl_toString(FreeA) `+ " [" + str$( fl_List(FreeA).firstItem ) + " -> " + str$( fl_List(FreeA).lastItem ) + "]"
center text x2, 450, "Free Items: " + fl_toString(FreeB) `+ " [" + str$( fl_List(FreeB).firstItem ) + " -> " + str$( fl_List(FreeB).lastItem ) + "]"
text x1 - 80, 480, "New:"
text x2 - 80, 480, "New:"
if DrawBox(x1-8, 480, x1+8, 496, 0)=1
tmp = fl_revive(FreeA)
if tmp > 0 then ListA( tmp ) = 1
waitForMouse = 1
endif
if DrawBox(x2-8, 480, x2+8, 496, 0)=1
tmp = fl_revive(FreeB)
if tmp > 0 then ListB( tmp ) = 1
waitForMouse = 1
endif
`debug()
ink 0xA0FFFFFF,0
print "Press Elements to delete them, press button below to recreate items if available"
rem Draw
sync
if waitForMouse = 1
while mouseclick() : endwhile
waitForMouse = 0
endif
loop
function DrawBox(x1,y1,x2,y2,v)
ink 0xFFFFFFFF,0
box x1, y1, x2, y2
r = 0
ink 0xFF202020,0
if mousex() >= x1 and mousex() <= x2
if mousey() >= y1 and mousey() <= y2
r = mouseclick()
ink 0xFF404040,0
endif
endif
box x1+2, y1+2, x2-2, y2-2
if v
ink 0xFFFFFFFF,0
box x1+4, y1+4, x2-4, y2-4
endif
endfunction r
function debug()
ink 0xFFFF0000,0
print "Stored Items: ", fl_count
for i = 1 to fl_count
print i, ": ", fl_item(i).key, " [List ", fl_item(i).list, "] -> '", fl_item(i).nxt, ": ", fl_item( fl_item(i).nxt ).key, "'"
next i
endfunction
#constant fl_ITEMSTEP = 1024
function fl_init()
rem List Array
global fl_listCount as integer = 0
dim fl_List(0) as fl_ListType
rem Item Array
global fl_capacity as integer = fl_ITEMSTEP
global fl_count as integer = 0
dim fl_item(fl_capacity) as fl_ItemType
endfunction
type fl_ListType
firstItem as integer
lastItem as integer
items as integer
endtype
type fl_ItemType
list as integer
key as integer
prev as integer
nxt as integer
endtype
function fl_newList()
ID = fl__newList()
fl_List(ID).lastItem = 0
i = fl_register(ID,0)
fl_List(ID).firstItem = i
fl_List(ID).items = 0
endfunction ID
function fl_register(list,key)
ID = fl__newItem()
fl_item(ID).key = key
fl_item(ID).prev = fl_list(list).lastItem
fl_item(fl_list(list).lastItem).nxt = ID
fl_item(ID).nxt = 0
fl_item(ID).list = list
inc fl_list(list).items
fl_list(list).lastItem = ID
endfunction ID
function fl_revive(list)
if fl_List(list).items > 0
last = fl_List(list).lastItem
ID = fl_Item( last ).key
fl_List(list).lastItem = fl_Item(last).prev
fl_Item( fl_Item(last).prev ).nxt = 0
dec fl_list(list).items
rem Make sure there's no empty spot in the free list
if last < fl_count
fl__move(fl_count, last)
endif
dec fl_count
else
ID = -1
endif
endfunction ID
function fl_toString(list)
s$ = fl__toString( fl_Item( fl_List(list).firstItem ).nxt )
endfunction s$
function fl__toString(item)
if item = 0
s$ = ""
else
s$ = str$(fl_item(item).key) + " " + fl__toString( fl_item(item).nxt )
endif
endfunction s$
function fl__newList()
inc fl_ListCount
array insert at bottom fl_List()
ID = fl_ListCount
endfunction ID
function fl__newItem()
inc fl_count
ID = fl_count
if fl_count > fl_capacity
inc fl_capacity, fl_ITEMSTEP
array insert at bottom fl_item(), fl_ITEMSTEP
endif
endfunction ID
function fl__move(src,trg)
list = fl_item(src).list
fl_item(trg).list = list
fl_item(trg).key = fl_item(src).key
fl_item(trg).prev = fl_item(src).prev
fl_item(trg).nxt = fl_item(src).nxt
fl_item( fl_item(src).prev ).nxt = trg
fl_item( fl_item(src).nxt ).prev = trg
if fl_list( list ).lastItem = src
fl_list( list ).lastItem = trg
endif
if fl_list( list ).firstItem = src
fl_list( list ).firstItem = trg
endif
endfunction
Now to get back to the scenario describes in the beginning, here's some pseudo code:
1. Deleting dead units
function addUnit()
array insert at bottom Unit()
ID = array count(Unit())
endfunction ID
function killUnit(ID)
array delete element Unit(), ID
endfunction
function handleUnits(ID)
for u = 1 to array size(Unit())
handleUnit(u)
next u
endfunction
Problem: Array IDs get messed up quickly and the whole system gets inconsistent as soon as you're using values that refer to those array IDs.
2. exist-Flag, first Version: dead units are kept in the array
function addUnit()
array insert at bottom Unit()
ID = array count(Unit())
Unit(ID).exist = 1
endfunction ID
function killUnit(ID)
Unit(ID).exist = 0
endfunction
function handleUnits(ID)
for u = 1 to array size(Unit())
if Unit(u).exist then handleUnit(u)
next u
endfunction
Problem: After some time the array gets huge, generating much overhead in the handleUnits-function since a ton of dead units have to be traversed, although they are not actually needed.
3. exist-Flag, second Version: dead units are replaced by searching them when adding a new unit
function addUnit()
for ID = 1 to array count(Unit())
if Unit(ID).exist = 0 then exit
next ID
if ID > array count(Unit())
array insert at bottom Unit()
endif
Unit(ID).exist = 1
endfunction ID
function killUnit(ID)
Unit(ID).exist = 0
endfunction
function handleUnits(ID)
for u = 1 to array size(Unit())
if Unit(u).exist then handleUnit(u)
next u
endfunction
Problem: Searching for free IDs takes some time. Usually you won't notice that because it's probably a matter of less than a milisecond, but still there may be cases when extensive data has to be handled this way and the search process may become the bottle neck.
4. exist-Flag, third and final Version: Using a free list
function addUnit()
ID = fl_revive(UnitFreeList)
if ID < 0
array insert at bottom Unit()
ID = array count(Unit())
endif
Unit(ID).exist = 1
endfunction ID
function killUnit(ID)
Unit(ID).exist = 0
fl_register(UnitFreeList,ID)
endfunction
function handleUnits(ID)
for u = 1 to array size(Unit())
if Unit(u).exist then handleUnit(u)
next u
endfunction
Problem: Solved.
