 |
Castle Paradox
|
| View previous topic :: View next topic |
| Author |
Message |
TMC
On the Verge of Insanity
Joined: 05 Apr 2003
Posts: 3240
Location: Matakana
|
 Posted: Fri Nov 18, 2005 5:36 pm Post subject: |
 |
|
| Quote: | | You're right; it should be sorted by TTL instead of the cycle value. However, if integer wrapping were ignored, the cycle value would be identical to the TTL, right? |
Yes.
Actually, if you use a really large wraparound value like 32000 then wraparound will happen so infrequently that yuo could speed up your sorting by not doing a TTL check. However, this complicates pulling the next object out of the sorted list: you have to be ready to traverse the entire list if the cycle execution time of the first one is less than your current cycle time. I think that's a bad idea though.
IM's logic on sorting the list not saving time caught me out. However, I just remembered something: the next execution time variable. On an unsorted list, you have to check every element both against the current timer to see if it must be executed and against the next timer, and adjust it if you find a closer match. So in reality, you have to do 2 checks per element when tranversing an unsorted list. This tips the balance in favour of a sorted list, where the next execution time is simple to extract.
For example, this might be your code for traversing an unsorted list
| Code: | global variable (next execute)
variable (element ptr, cycle, temp)
element ptr := first element #a global variable
next execute := -1
while (element ptr) do ( # or how ever else you indicate end of list
cycle := read global (element ptr + EXECUTE TIME) # depends on the structue of an element
if (cycle == current cycle) then (
# execute and delete
) else (
# update next execution cycle global
temp := cycle -- current cycle
if (temp << 0) then (temp += 1000)
if (temp << next execute) then (next execute := cycle)
)
element ptr := read global (element ptr + NEXT ELEMENT)
) |
(Of course, you'll need to keep track of extra pointers for deleting)
| Quote: | | Wait, how does this work? If I sort the linked list by TTL, then the first element(s) will always be the one to be executed (if any are to be executed at all). If the management script just continues down the list until it hits an element that shouldn't be executed, it gets nearly 1 execution per element traversal. However, the first few elements in a heap are not at all guaranteed to be the ones to be executed, right? |
We are sorting the heap by TTL, so the root is always the next thing that needs execution, the next after that is one of its children, etc, just like a sorted list.
| Quote: | | Additionally, if I have a pointer to the last element in the sorted list, then I will very rarely need to traverse the entire list in order to insert a new element. I mean, it could still happen, but not likely. |
You mean, you expect new script calls will probably go on the end of the list, so are planning on checking the last element first?
_________________
"It is so great it is insanely great." |
|
| Back to top |
|
 |
Inferior Minion
Metric Ruler
Joined: 03 Jan 2003
Posts: 741
Location: Santa Barbara, CA
|
| Posted: Fri Nov 18, 2005 8:36 pm Post subject: |
|
|
| Mr B wrote: | | Inferior Minion wrote: | | The execution process is linear in a linked list. The more elements in your list, the longer the execution time. That's not the case in a heap. It's logarithmic. Your run time is log(n). For your application, the heap takes care of 2 - 6 much more efficiently than the linked list. |
Wait, how does this work? If I sort the linked list by TTL, then the first element(s) will always be the one to be executed (if any are to be executed at all). If the management script just continues down the list until it hits an element that shouldn't be executed, it gets nearly 1 execution per element traversal. However, the first few elements in a heap are not at all guaranteed to be the ones to be executed, right? |
First off, I mean total execution time, for insertion and deletion. Yes, the sorted linked list might take 2 executions to delete the head and update the list, but it'll take longer to sort the list than it would to insert it into a heap.
I don't think you fully understand what a heap is. A heap is a tree. Each node has a left branch and a right branch. However, unlike a binary tree where the left child is smaller than the parent and the right child is larger, a heap stipulates that both the left and right child are larger than the parent. The tree is filled from left to right across each level, which allows for an array implementation where the parent's index * 2 represents the left child, index * 2 + 1 is the right child.
Graphical Representation:
Array: 5, 10, 12, 14
Array: 5, 10, 12, 14, 8
Note: You simply insert at the very end of the array to find the next available node
Array: 5, 8, 12, 14, 10
Since 5 is less than 8, execution ends
Array: 10, 8, 12, 14 (5)
Note: this can be accomplished by simply swapping the first and last element using your swap code. Then decrement the number of elements and the next element written will overwrite 5.
Array: 8, 10, 12, 14
Since 10 is less than 14, execution ends.
Now to try and prove my point with a better example. Insert 11 and use the array as both a Linked List and a heap.
You have two options with the linked list....sort from the front to back or from back to front. In this case, it doesn't matter. You have to check 3 elements before you're sure 11 goes between 12 and 10.
This heap does no swaps, but in a generic heap of 4 elements, the maximum number of swaps is 2.
Now you have the arrays as follows:
Linked List: 8, 10, 11, 12, 14
Heap: 8, 10, 12, 14, 11
To make things interesting, we'll assume you're almost always inserting at the back of the list (starting from the tail when you sort). We'll insert 7. (Note: This is the same as sorting from the head and inserting 15, but you don't get to see the heap do any work). I should also mention that to do your linked list this way, you need a doubly-linked list, otherwise you can't traverse backwards.
Linked List:
Checks 14, smaller, moves left.
Checks 12, smaller, moves left
Checks 11, smaller, moves left
Checks 10, smaller, moves left
Checks 8, smaller, moves left
Null, inserts.
Array: 7, 8, 10, 11, 12, 14
Heap:
The new array woud be 8, 10, 12, 14, 11, 7. Therefore 7 i s the left child of 12.
Checks it's parent, 7 < 12, swaps.
Checks it's parent, 7 < 8, swaps.
It's at the root, finished.
That's worst case for a heap of 4 - 7 elements. 8 - 15 has 1 more swap. 16 - 20 has 2 more. If you're constantly adding the largest elements, they're already at the bottom of the list and won't have to propogate back up the root (which would only take 4 swaps max). Deletion is a downward propogation, so the maximum number of swaps remains the same. Even though the sorted list takes less time to delete, you can do a heap insert and a heap delete in the same time it takes to do a single linked list insertion.
| Mr B wrote: | | Additionally, if I have a pointer to the last element in the sorted list, then I will very rarely need to traverse the entire list in order to insert a new element. I mean, it could still happen, but not likely. |
That means you're throwing in an extra check every insertion to see if it belongs at the very end, then traversing the tree if it doesn't. Since you're doing a singly-linked list, you cannot traverse the tree backwards and must find the point of insertion starting from the head of the list.
| The Mad Cacti wrote: | | Mr.B wrote: | | You're right; it should be sorted by TTL instead of the cycle value. However, if integer wrapping were ignored, the cycle value would be identical to the TTL, right? |
Yes.
Actually, if you use a really large wraparound value like 32000 then wraparound will happen so infrequently that yuo could speed up your sorting by not doing a TTL check. However, this complicates pulling the next object out of the sorted list: you have to be ready to traverse the entire list if the cycle execution time of the first one is less than your current cycle time. I think that's a bad idea though. |
No. The Cycle value and the TTL are different. TTL is the Cycle Value - the current cycle counter. That means it decreases every cycle. You could simply sort by Cycle Value, but it gets really tricky when the cycle does loop. All sorts of special cases and I can't see it being anything other than a headache to keep track of.
However, pointing this out did make me realize the heap insertion code TMC and I used needs altering. Right now you have to give it the Cycle Value, when it makes more sense to give the script a TTL and then calculate when it needs to be executed based on the counter. I'll edit that and repost in a bit.
| The Mad Cacti wrote: | | IM's logic on sorting the list not saving time caught me out. However, I just remembered something: the next execution time variable. On an unsorted list, you have to check every element both against the current timer to see if it must be executed and against the next timer, and adjust it if you find a closer match. So in reality, you have to do 2 checks per element when tranversing an unsorted list. This tips the balance in favour of a sorted list, where the next execution time is simple to extract. |
Very good point. I completely neglected the fact that Mr. B was keeping a "next execution" variable to minimize the master loop runtime. I still think a heap is much better suited for this application though.
Edit: Modified the code
| Code: |
global variable (
1, current counter
2, stack ptr
3, num elements
)
define constant (
100, STACK BASE
120, ARRAY BASE
160, FREE ELEMENTS BASE
5 , ELEMENT VARS
)
#Array Model:
# ARRAY BASE: Cycle Execution Time
# + 1: Element Base Pointer
#Element Model:
# ELEMENT BASE: Script ID
# + 1: Script Arg 1
# + 2: Script Arg 2
# + 3: Script Arg 3
# + 4: Script Arg 4
#example of your master loop
script, master, begin
variable (i)
while ( i << 20 ) (
# Write the available element base locations into the stack
write global ( STACK BASE + stack ptr, FREE ELEMENTS BASE + i * ELEMENT VARS )
i += 1
stack ptr += 1
)
while (1) do (
while (num elements >> 0,and,read global (ARRAY BASE) == current counter) do (
#process element at read global (ARRAY BASE + 1)
# As far as processing goes, ARRAY BASE + 1 stores the global for the element base
# See the Element Model for accessing the global variables
delete heap root ()
)
wait
current counter := (current counter + 1), mod, 1000
)
end
#inserts values into the heap, deals with the stack, and returns a ptr to
#an element to fill with data
script, new element, live time, begin
variable (element ptr, run time)
# find a free element
stack ptr -= 1
# Any elements left?
if (stack ptr << 0) then () #throw an error?
element ptr := read global (STACK BASE + stack ptr)
run time := (current counter + live time) , mod, 1000
# insert into heap (at the bottom)
variable (cur ptr, parent ptr)
write global (ARRAY BASE + num elements * 2, run time)
write global (ARRAY BASE + num elements * 2 + 1, element ptr)
cur ptr := num elements
num elements += 1
# sort heap from bottom up
while (cur ptr) do ( #until reach root
# find parent
parent ptr := (cur ptr -- 1) / 2
live parent := read global (ARRAY BASE + parent ptr * 2) -- current counter
if (live parent << 0) then (live parent += 1000)
if (live parent >> live time) then (
live time := live parent
heap swap (ARRAY BASE + parent ptr * 2, ARRAY BASE + heap ptr * 2)
cur ptr := parent ptr
) else (cur ptr := 0) #jump out of loop
)
return (element ptr)
end
# after pulling a reference off the heap and processing the element, call this is it is done
script, delete heap root, begin
# Any elements in the heap?
if ( num elements <= 0 ) then () #throw an error?
#stick the element base pointer back on the stack
write global (STACK BASE + stack ptr, read global (ARRAY BASE + 1))
stack ptr += 1
#put last heap node at the root
num elements -= 1
write global (ARRAY BASE, read global (ARRAY BASE + num elements * 2))
write global (ARRAY BASE + 1, read global (ARRAY BASE + num elements * 2 + 1))
#sort heap from top down
variable (cur ptr, child1, child2, live1, live2, live parent)
cur ptr := 0
live parent := read global (ARRAY BASE) -- current counter
if (live parent << 0) then (live parent += 1000)
while (cur ptr * 2 << num elements) do ( #has children
child1 := cur ptr * 2 + 1
child2 := child1 + 1
live1 := read global (ARRAY BASE + child1 * 2) -- current counter
if (live1 << 0) then (live1 += 1000)
#if more than 1 child, find the lowest life
if (child2 <= num elements) then (
live2 := read global (ARRAY BASE + child2 * 2) -- current counter
if (live2 << 0) then (live2 += 1000)
if (live1 >> live2) then (child1 := child2, live1 := live2)
)
if (live parent >> live1) then (
heap swap (ARRAY BASE + child1 * 2, ARRAY BASE + cur ptr * 2)
cur ptr := child1
live parent := live1
) else (cur ptr := 999) #quit
)
end
script, heap swap, ptr1, ptr2, begin
variable (temp)
temp := read global (ptr1)
write global (ptr1, read global(ptr2))
write global (ptr2, temp)
temp := read global (ptr1 + 1)
write global (ptr1 + 1, read global(ptr2 + 1))
write global (ptr2 + 1, temp)
end |
This should allow you to insert nodes by giving the TTL. The heap will work out when the script needs to be run based on the offest (e.g. "Insert this script and run it in 5 ticks" instead of "insert this script and run it when the cycle counter is at 100").
_________________
|
|
| Back to top |
|
|
TMC
On the Verge of Insanity
Joined: 05 Apr 2003
Posts: 3240
Location: Matakana
|
| Posted: Sat Nov 19, 2005 3:24 am Post subject: |
|
|
IM is putting such effort into this. I hope he doesn't wind up a teacher.  I've definitely learnt something though.
| Inferior Minion wrote: |
| The Mad Cacti wrote: | | Mr.B wrote: | | You're right; it should be sorted by TTL instead of the cycle value. However, if integer wrapping were ignored, the cycle value would be identical to the TTL, right? |
Yes.
Actually, if you use a really large wraparound value like 32000 then wraparound will happen so infrequently that yuo could speed up your sorting by not doing a TTL check. However, this complicates pulling the next object out of the sorted list: you have to be ready to traverse the entire list if the cycle execution time of the first one is less than your current cycle time. I think that's a bad idea though. |
No. The Cycle value and the TTL are different. TTL is the Cycle Value - the current cycle counter. That means it decreases every cycle. You could simply sort by Cycle Value, but it gets really tricky when the cycle does loop. All sorts of special cases and I can't see it being anything other than a headache to keep track of. |
Whoops, I misunderstood the question. I thought he asked "would the sorting (as in final order) be identical".
_________________
"It is so great it is insanely great." |
|
| Back to top |
|
|
Mr B
Joined: 20 Mar 2003
Posts: 382
|
| Posted: Sat Nov 19, 2005 11:27 am Post subject: |
|
|
Urg. I knew that heaps were trees, but I forgot they were sorted like that...my bad.
I pulled out my programming literature from last night and looked up heap implementation, and I realize now that it's the best thing for the job (took me long enough!). I will save a lot of space per element by not needing pointers, and I won't need the stack b/c the heap uses an array.
As far as TTL goes, the only thing that I can think to do us have each element contain a cycle value showing when it is to be executed. When comparing child/child or child/parent cycles, the lowest value percolates up -- except when one value is less than the current cycle (which means that it looped around) and the other isn't. If they're both less than the current cycle, then the lowest one percolates up again. I am trying to figure out a way to check for these three situations without using more than one if-then statement.
Am I understanding this correctly? It has been a couple of years since I really thought about heaps... |
|
| Back to top |
|
|
Inferior Minion
Metric Ruler
Joined: 03 Jan 2003
Posts: 741
Location: Santa Barbara, CA
|
| Posted: Sat Nov 19, 2005 12:32 pm Post subject: |
|
|
| Mr B wrote: | Urg. I knew that heaps were trees, but I forgot they were sorted like that...my bad.
I pulled out my programming literature from last night and looked up heap implementation, and I realize now that it's the best thing for the job (took me long enough!). I will save a lot of space per element by not needing pointers, and I won't need the stack b/c the heap uses an array.
As far as TTL goes, the only thing that I can think to do us have each element contain a cycle value showing when it is to be executed. When comparing child/child or child/parent cycles, the lowest value percolates up -- except when one value is less than the current cycle (which means that it looped around) and the other isn't. If they're both less than the current cycle, then the lowest one percolates up again. I am trying to figure out a way to check for these three situations without using more than one if-then statement.
Am I understanding this correctly? It has been a couple of years since I really thought about heaps... |
Check out the code I modified from TMC's initial post. It does make use of a stack, which allows for easy altering of the elements stored in the heap.
The array for the heap is set up as follows:
| Code: |
[ -------Array Element 1------ ][ -------Array Element 2------ ]...
[Global 120][ ---Global 121--- ][Global 122][ ---Global 123--- ]...
[ Run Time ][ Element Pointer ][ Run Time ][ Element Pointer ]...
|
I'm not sure you'll be saving much time by checking to see if the Run Time is less than the current cycle value. Currently, the code does Run Time - Current Count and then adds 1000 if it's less than 0. You're saving the code from doing a subtraction during an assignment operation, which is negligable. Altering the code to read the global and if it's less than the current count, add 1000 - current count. I don't think you'll see any increase in speed, but that really depends on how effecient HS is at doing subtraction .
I've read through the code again and noticed a few errors (We were swapping the TTL value when we swapped the actual elements, which we didn't want to do), so here's an updated version.
| Code: | global variable (
1, current counter
2, stack ptr
3, num elements
)
define constant (
100, STACK BASE
120, ARRAY BASE
160, FREE ELEMENTS BASE
5 , ELEMENT VARS
)
#Array Model:
# ARRAY BASE: Cycle Execution Time
# + 1: Element Base Pointer
#Element Model:
# ELEMENT BASE: Script ID
# + 1: Script Arg 1
# + 2: Script Arg 2
# + 3: Script Arg 3
# + 4: Script Arg 4
#example of your master loop
script, master, begin
variable (i)
while ( i << 20 ) (
# Write the available element base locations into the stack
write global ( STACK BASE + stack ptr, FREE ELEMENTS BASE + i * ELEMENT VARS )
i += 1
stack ptr += 1
)
while (1) do (
while (num elements >> 0,and,read global (ARRAY BASE) == current counter) do (
#process element at read global (ARRAY BASE + 1)
# As far as processing goes, ARRAY BASE + 1 stores the global for the element base
# See the Element Model for accessing the global variables
delete heap root ()
)
wait
current counter := (current counter + 1), mod, 1000
)
end
#inserts values into the heap, deals with the stack, and returns a ptr to
#an element to fill with data
script, new element, live time, begin
variable (element ptr, run time)
# find a free element
stack ptr -= 1
# Any elements left?
if (stack ptr << 0) then () #throw an error?
element ptr := read global (STACK BASE + stack ptr)
run time := (current counter + live time) , mod, 1000
# insert into heap (at the bottom)
variable (cur ptr, parent ptr)
write global (ARRAY BASE + num elements * 2, run time)
write global (ARRAY BASE + num elements * 2 + 1, element ptr)
cur ptr := num elements
num elements += 1
# sort heap from bottom up
while (cur ptr) do ( #until reach root
# find parent
parent ptr := (cur ptr -- 1) / 2
live parent := read global (ARRAY BASE + parent ptr * 2) -- current counter
if (live parent << 0) then (live parent += 1000)
if (live parent >> live time) then (
heap swap (ARRAY BASE + parent ptr * 2, ARRAY BASE + cur ptr * 2)
cur ptr := parent ptr
) else (cur ptr := 0) #jump out of loop
)
return (element ptr)
end
# after pulling a reference off the heap and processing the element, call this is it is done
script, delete heap root, begin
# Any elements in the heap?
if ( num elements <= 0 ) then () #throw an error?
#stick the element base pointer back on the stack
write global (STACK BASE + stack ptr, read global (ARRAY BASE + 1))
stack ptr += 1
#put last heap node at the root
num elements -= 1
write global (ARRAY BASE, read global (ARRAY BASE + num elements * 2))
write global (ARRAY BASE + 1, read global (ARRAY BASE + num elements * 2 + 1))
#sort heap from top down
variable (cur ptr, child1, child2, live1, live2, live parent)
cur ptr := 0
live parent := read global (ARRAY BASE) -- current counter
if (live parent << 0) then (live parent += 1000)
while (cur ptr * 2 << num elements) do ( #has children
child1 := cur ptr * 2 + 1
child2 := child1 + 1
live1 := read global (ARRAY BASE + child1 * 2) -- current counter
if (live1 << 0) then (live1 += 1000)
#if more than 1 child, find the lowest life
if (child2 <= num elements) then (
live2 := read global (ARRAY BASE + child2 * 2) -- current counter
if (live2 << 0) then (live2 += 1000)
if (live1 >> live2) then (child1 := child2, live1 := live2)
)
if (live parent >> live1) then (
heap swap (ARRAY BASE + child1 * 2, ARRAY BASE + cur ptr * 2)
cur ptr := child1
) else (cur ptr := 999) #quit
)
end
script, heap swap, ptr1, ptr2, begin
variable (temp)
temp := read global (ptr1)
write global (ptr1, read global(ptr2))
write global (ptr2, temp)
temp := read global (ptr1 + 1)
write global (ptr1 + 1, read global(ptr2 + 1))
write global (ptr2 + 1, temp)
end |
As I said in an earlier post, when using this code you need to modify the master loop to have it process your elements when it's time to execute them. The following code would be used to insert an element into the heap:
| Code: | variable(temp)
temp := new element( Number of cycles before the script should be run )
write global( temp, Script ID )
write global( temp + 1, Arg1 )
write global( temp + 2, Arg2 )
write global( temp + 3, Arg3 )
write global( temp + 4, Arg4 ) |
Just want to note that you're passing the TTL, not the value the counter should be at when you run the script. I.E. temp := new element( 11 ) means "execute this element in 11 cycles (current count + 11)", not "execute this element when current count == 11"
_________________
|
|
| Back to top |
|
|
Mr B
Joined: 20 Mar 2003
Posts: 382
|
| Posted: Sun Nov 20, 2005 4:16 pm Post subject: |
|
|
| So, the only purpose of the stack is to allow heap elements to be modified after they have been inserted? |
|
| Back to top |
|
|
Inferior Minion
Metric Ruler
Joined: 03 Jan 2003
Posts: 741
Location: Santa Barbara, CA
|
| Posted: Sun Nov 20, 2005 5:45 pm Post subject: |
|
|
| Mr. B wrote: | | So, the only purpose of the stack is to allow heap elements to be modified after they have been inserted? |
The stack serves 3 purposes.
1. Keeps track of available "memory" in the form of unused global variables that can be used as the base of an element
2. Allows an element to be an arbitrary size without having to alter the heap code.
3. Speeds up swapping by only requiring 2 variables to be swapped.
Number 3 is the most important, since swapping occurs so frequently. Your heap elements consist of 6 elements. Since the heap is stored by the Run Time, it's better to have immediate access to that variable. Therefore, TMC set up the array as I mentioned in my last post, with the Run Time directly accessed in the first slot and a pointer to the rest of the variables in the second slot.
Without the pointer, you'd keep swapping 6 variables instead of 2.
The reason TMC returns the element pointer and has you manually set the last 5 variables is to allow the heap element to be altered without having to change the function call to new element or alter the heap code in any way. It makes for a much more flexible heap.
_________________
|
|
| Back to top |
|
|
Mr B
Joined: 20 Mar 2003
Posts: 382
|
| Posted: Fri Nov 25, 2005 11:56 am Post subject: |
|
|
Okay; I've been writing my own scripts to do the job (because it helps me feel closer to the work, and I am more familiar with its strengths and weaknesses).
I have come up with a problem. Are Binary Heaps 0-based or 1-based? The scripts posted here are 0-based, but the book I have is 1-based, and the math seems to bear it out. Only on a 1-based Heap is the first child equal to the parent * 2...right?
I ask because I've been writing my scripts as 0-based without even paying attention to the structure the book set out. I am not at the point where I can test the scripts myself to see if they'd work that way.
Thanks,
-B |
|
| Back to top |
|
|
Mr B
Joined: 20 Mar 2003
Posts: 382
|
| Posted: Fri Nov 25, 2005 12:20 pm Post subject: |
|
|
Here's what I've done for two of the main Heap scripts (there is one more to do, "process actions," that actually calls the "deleteMin" script).
| Code: |
script, insert, run_time, script_ID, val1, val2, val3, val4, begin
# This script creates a new element in the Heap and in the Elements.
if(actions_heap_elements << ACTIONS_HEAP_MAX_ELEMENTS) then
(
# all pointer variables are to point to elements, NOT globals.
# 1st element = 1, 2nd element = 2, etc. (except "element_ptr")
variable(element_ptr, heap_ptr, heap_ptr_parent, heap_ptr_cycle, heap_ptr_parent_cycle)
element_ptr := pop # get free Element element
actions_heap_elements += 1 # enlarge Heap
heap_ptr := actions_heap_elements # point to new Heap element
# plenish Element element elements (teh lol?)
write global(ACTIONS_ELEMENTS_BASE + element_ptr * ACTIONS_ELEMENTS_ELEMENT_SIZE, script_ID)
write global(ACTIONS_ELEMENTS_BASE + element_ptr * ACTIONS_ELEMENTS_ELEMENT_SIZE + 1, val1)
write global(ACTIONS_ELEMENTS_BASE + element_ptr * ACTIONS_ELEMENTS_ELEMENT_SIZE + 2, val2)
write global(ACTIONS_ELEMENTS_BASE + element_ptr * ACTIONS_ELEMENTS_ELEMENT_SIZE + 3, val3)
write global(ACTIONS_ELEMENTS_BASE + element_ptr * ACTIONS_ELEMENTS_ELEMENT_SIZE + 4, val4)
# plenish Heap element elements
write global(ACTIONS_HEAP_BASE + heap_ptr * ACTIONS_HEAP_ELEMENT_SIZE, run_time)
write global(ACTIONS_HEAP_BASE + heap_ptr * ACTIONS_HEAP_ELEMENT_SIZE, element_ptr)
# sort heap from bottom to top
heap_ptr_parent := heap_ptr / 2 # redundant, but necessary to allow loop to start out
while(heap_ptr >> 1) do # while has parent
(
heap_ptr_parent := heap_ptr / 2
heap_ptr_parent_cycle := read global(ACTIONS_HEAP_BASE + heap_ptr_parent * ACTIONS_HEAP_ELEMENT_SIZE)
heap_ptr_cycle := read global(ACTIONS_HEAP_BASE + heap_ptr * ACTIONS_HEAP_ELEMENT_SIZE)
# global 80 contains the current cycle (see note at top of file)
if((heap_ptr_cycle >> read global(80)),and,(heap_ptr_cycle << heap_ptr_parent_cycle)) then
( swap (heap_ptr, heap_ptr_parent) )
else (
if((heap_ptr_parent_cycle << read global(80)),and,(heap_ptr_cycle << heap_ptr_parent_cycle)) then
( swap (heap_ptr, heap_ptr_parent) )
else ( heap_ptr := 0 ) # nothing more to swap
)
)
) else # insufficient Heap space
( return (-1) )
end
script, deleteMin, begin
# this script deletes the lowest value element in the Heap and then fixes Heap order
# if there at least one element to delete
if(actions_heap_elements >> 0) then
(
variable(heap_ptr, child1, child2, heap_ptr_cycle, cycle1, cycle2)
swap (actions_heap_elements, 0) # swap first w/ last Heap element
actions_heap_elements -= 1 # reduce size to reflect deletedness
heap_ptr := 0
# sort heap from top down
while(heap_ptr * 2 <= actions_heap_elements) do # while has at least one child
(
child1 := heap_ptr * 2 # that's just how Heaps work
child2 := child1 + 1 # first child + 1 Heap element
heap_ptr_cycle := read global(ACTIONS_HEAP_BASE + heap_ptr * ACTIONS_HEAP_ELEMENT_SIZE)
cycle1 := read global(ACTIONS_HEAP_BASE + child1 * ACTIONS_HEAP_ELEMENT_SIZE)
# if more than one child actually exists
if(child2 <= actions_heap_elements) then
(
cycle2 := read global(ACTIONS_HEAP_BASE + child2 * ACTIONS_HEAP_ELEMENT_SIZE)
# global 80 contains the current cycle (see note at top of file)
if((cycle2 << cycle1),and,(cycle2 >> read global(80))) then
(
child1 := child2
cycle1 := cycle2
)
)
# global 80 contains the current cycle (see note at top of file)
if((cycle1 << heap_ptr_cycle),and,(cycle1 >> read global(80))) then
(
swap(heap_ptr, child1)
heap_ptr := child1
) else ( heap_ptr := 999 ) # quit sorting loop
)
) else ( return (-1) ) # no more elements to delete
end
|
As was already discussed, I have three different data structures running here. One is the Elements, which is just an array holding the script ID and the four variables. One is the Stack, which holds unused Element elements. The last is the Heap, with which I am mostly concerned.
I know that a lot of the scripting is not mathematically optimized, but I'll sacrifice that for intelligability until I'm after the actual "figuring it all out" stage. |
|
| Back to top |
|
|
Inferior Minion
Metric Ruler
Joined: 03 Jan 2003
Posts: 741
Location: Santa Barbara, CA
|
| Posted: Fri Nov 25, 2005 3:26 pm Post subject: |
|
|
To answer your question, it's arbitrary which element you use as the base, as long as you work out the math correctly to support it and build your array to follow suit.
Most implementations throw away the first element (0) and use 1 as the base of the array. This allows the parent to be array_element / 2. To use 0 as the base, you simply shift left 1 element: parent = (array_element - 1 ) / 2.
The second issue you need to address is the array element size. In a basic heap, there is only one value associated with each array element. You need 2.
| Mr. B wrote: | | Code: |
# plenish Heap element elements
write global(ACTIONS_HEAP_BASE + heap_ptr * ACTIONS_HEAP_ELEMENT_SIZE, run_time)
write global(ACTIONS_HEAP_BASE + heap_ptr * ACTIONS_HEAP_ELEMENT_SIZE, element_ptr)
|
|
You're overwriting your run time with the element pointer right now. To fix this, you need to add another level of abstraction to your array.
Instead of:
| Code: |
[ 0 ] [ 1 ] [ 2 ] [ 3 ] ...
[ var ] [ var ] [ var ] [ var ] ...
|
You want:
| Code: |
[ 0 ] [ 1 ] [ 2 ] ...
[ 0 ][ 1 ] [ 2 ][ 3 ] [ 4 ][ 5 ] ...
[ run time ][ element ptr ] [ run time ][ element ptr ] [ run time ][ element ptr ] ...
|
Where the first row is the virtual array element, the second row is the actual array element, and the 3rd row is what variable is stored in that element.
To accomplish this, you keep track of the virtual array pointers, then multiply by 2 , which I think you're doing using ACTIONS_HEAP_ELEMENT_SIZE (I just noticed that when going to change your code, but didn't want to delete my ASCII explanation, so yeah....you just missed a "+ 1"), whenever you want to interact with the actual elements, which changes your code to the following:
| Code: |
# plenish Heap element elements
write global(ACTIONS_HEAP_BASE + heap_ptr * ACTIONS_HEAP_ELEMENT_SIZE, run_time)
write global(ACTIONS_HEAP_BASE + heap_ptr * ACTIONS_HEAP_ELEMENT_SIZE + 1, element_ptr)
|
Moving onto the actual sorting.
First off, you're using run_time directly in your heap. That's fine, but it means you have to manually calculate when the script should be run prior to calling the insertion function. You might consider sending the TTL offset and calculating the runtime within the insertion (my heavily rooted OO programming makes me want to do that ).
Second, your current sorting algorithm doesn't fully work, maybe.
| Mr. B wrote: | | Code: |
# global 80 contains the current cycle (see note at top of file)
if((heap_ptr_cycle >> read global(80)),and,(heap_ptr_cycle << heap_ptr_parent_cycle)) then
( swap (heap_ptr, heap_ptr_parent) )
else (
if((heap_ptr_parent_cycle << read global(80)),and,(heap_ptr_cycle << heap_ptr_parent_cycle)) then
( swap (heap_ptr, heap_ptr_parent) )
else ( heap_ptr := 0 ) # nothing more to swap
)
)
|
|
You need 1 more if:
heap_ptr_cycle >> read global(80) && heap_ptr_parent_cycle << read global(80)
Your delete code also needs a bit of adjusting to fit with the heap base being 0.
Child1 is no longer array_element * 2, but array_element*2+1. This also means your while loop needs a +1 stuck in it to make sure you're checking the right children.
| Code: | while(heap_ptr * 2 + 1<= actions_heap_elements) do # while has at least one child
(
child1 := heap_ptr * 2 + 1 # that's just how Heaps work
child2 := child1 + 1 # first child + 1 Heap element
|
Your code for checking if the two child runtimes seems to be missing quite a few ifs. It should really mimic the insertion ifs, when you think about it. Replace heap_ptr_cycle with cycle1 and heap_parent_cycle with cycle2. S ame is true for the final swap.
| Mr. B wrote: |
I know that a lot of the scripting is not mathematically optimized, but I'll sacrifice that for intelligability until I'm after the actual "figuring it all out" stage. |
The first place I'd start is that big if block for sorting the run times. You might consider throwing in another function that takes 2 variables and returns true if argument 1 would execute before argument 2, false otherwise. That way you're not copying and pasting those big if blocks all over the place. Apart from the things I pointed out, your code should work.
_________________
|
|
| Back to top |
|
|
Mr B
Joined: 20 Mar 2003
Posts: 382
|
| Posted: Mon Nov 28, 2005 3:00 pm Post subject: |
|
|
I've been spending the last few days attempting to track down some bugs. Hopefully I won't have to work tonight and will be able to concentrate for just a little longer. *sigh* Vacations are too short.
| IM wrote: | | Most implementations throw away the first element (0) and use 1 as the base of the array. This allows the parent to be array_element / 2. To use 0 as the base, you simply shift left 1 element: parent = (array_element - 1 ) / 2. |
I haven't converted to 0'th element use yet. I'm concentrating on tracking down these bugs first, but that will come.
| IM wrote: | | You're overwriting your run time with the element pointer right now. To fix this, you need to add another level of abstraction to your array. |
Fixed! And it took me a heck-of-a long time to figure it out, too. Darn cut'n'paste...
| IM wrote: | | heap_ptr_cycle >> read global(80) && heap_ptr_parent_cycle << read global(80) |
D'oh. You're right. I thought I had all of the possible combinations down. Thank you.
| IM wrote: | | The first place I'd start is that big if block for sorting the run times. You might consider throwing in another function that takes 2 variables and returns true if argument 1 would execute before argument 2, false otherwise. That way you're not copying and pasting those big if blocks all over the place. Apart from the things I pointed out, your code should work. |
Great!
I've been having a bit of problems with bugs in the last few days, but perhaps these things will fix that for me. If not...
I need to go through and clear out all of my error detection commands. It's just "show value" and "append number/ascii" stuff, but it's painful to look at. I think I've got something broken with the swap script I wrote...for some reason, the execution cycle value keeps getting set to -1...or something. I've got it to the point where a single entry will be executed with the correct delay, but multiple entries will all be executed at once, no matter what delay they're using. Oh well; the trama of code, eh?
Thank you for your pointers; I'll get crackin'. |
|
| Back to top |
|
|
Mr B
Joined: 20 Mar 2003
Posts: 382
|
| Posted: Sun Dec 04, 2005 4:24 pm Post subject: |
|
|
Yay! I think that I have finally got this functioning. It took nearly two weeks to script it and then slaughter my stupid bugs, but it seems to be working quite well.
I was having a problem with some of the deletion swaps, but it mysteriously went away somehow... I am still not entirely certain that the "actions heap soonest" script (which checks to see which has the lowest TTL) is logically correct. However, it seems to be working now.
Thanks for all of the help you guys have given me -- IM especially. I really apreciate it.
(the constants and globals are commented out b/c they now exist in a separate file)
| Code: |
## Global Variables:
#global variable, begin
# # Elements:
# #(none)
#
# # Stack:
# 90, actions_stack_elements
#
# # Heap:
# 91, actions_heap_elements
#end
## Global Constants:
#define constant, begin
# # Elements:
# 500, ACTIONS_ELEMENTS_BASE
# 50, ACTIONS_ELEMENTS_MAX_ELEMENTS
# 5, ACTIONS_ELEMENTS_ELEMENT_SIZE
#
# # Stack:
# 350, ACTIONS_STACK_BASE
# 50, ACTIONS_STACK_MAX_ELEMENTS
#
# # Heap:
# 400, ACTIONS_HEAP_BASE
# 50, ACTIONS_HEAP_MAX_ELEMENTS
# 2, ACTIONS_HEAP_ELEMENT_SIZE
#
#end
## Scripts by Group:
# General Scripts:
script, process Actions, begin
# This is the most important script for the Actions scripts.
# It looks at the stored Actions and executes them if necessary.
# global 80 contains the current cycle (see note at top of file)
while(read global(ACTIONS_HEAP_BASE) == read global(80),and,actions_heap_elements) do
(
actions run Action(read global(ACTIONS_HEAP_BASE + 1))
actions heap deleteMin ()
)
end
# Elements Scripts:
script, actions run Action, ref, begin
# This script runs an action by executing its script and
# passing it the action reference so it can get its own variables.
# This script may eventually be utilizing "import globals" stuff...
variable(ref2)
ref2 := ACTIONS_ELEMENTS_BASE + ref * ACTIONS_ELEMENTS_ELEMENT_SIZE
run script by ID(read global(ref2), ref)
end
# Stack Scripts:
script, actions stack push, element, begin,
# This script adds an unused Element element to the stack.
if(actions_stack_elements << ACTIONS_STACK_MAX_ELEMENTS) then
( actions_stack_elements += 1 )
write global(actions_stack_elements, element)
end
script, actions stack pop, begin
# This script returns an unused Element element for Heap & Element use.
if(actions_stack_elements) then
(
return(read global(actions_stack_elements))
actions_stack_elements -= 1
) else
( return(-1) )
end
# Heap scripts:
script, insert Action, run_time, script_ID, val1, val2, val3, val4, begin
# This script creates a new element in the Heap and in the Elements.
if((actions_heap_elements << ACTIONS_HEAP_MAX_ELEMENTS),and,actions_stack_elements) then
(
# all pointer variables are to point to elements, NOT globals.
# additionally, the Heap elements are referenced from 0, NOT 1
# 1st element = pointer value 0, 2nd element = 1, etc.
variable(element_ptr, heap_ptr, heap_ptr_parent)
element_ptr := actions stack pop () # get free Element element
actions_heap_elements += 1 # enlarge Heap
heap_ptr := actions_heap_elements -- 1 # point to new Heap element (--1 b/c element 1 is @ 0 offset)
# plenish Element element elements (teh lol?)
write global(ACTIONS_ELEMENTS_BASE + element_ptr * ACTIONS_ELEMENTS_ELEMENT_SIZE, script_ID)
write global(ACTIONS_ELEMENTS_BASE + element_ptr * ACTIONS_ELEMENTS_ELEMENT_SIZE + 1, val1)
write global(ACTIONS_ELEMENTS_BASE + element_ptr * ACTIONS_ELEMENTS_ELEMENT_SIZE + 2, val2)
write global(ACTIONS_ELEMENTS_BASE + element_ptr * ACTIONS_ELEMENTS_ELEMENT_SIZE + 3, val3)
write global(ACTIONS_ELEMENTS_BASE + element_ptr * ACTIONS_ELEMENTS_ELEMENT_SIZE + 4, val4)
# plenish Heap element elements
write global(ACTIONS_HEAP_BASE + heap_ptr * ACTIONS_HEAP_ELEMENT_SIZE, run_time)
write global(ACTIONS_HEAP_BASE + heap_ptr * ACTIONS_HEAP_ELEMENT_SIZE + 1, element_ptr)
# sort heap from bottom to top
heap_ptr_parent := (heap_ptr--1) / 2 # redundant, but necessary to allow loop to start out
while(heap_ptr >> 0) do # while has parent
(
heap_ptr_parent := (heap_ptr--1) / 2
if(actions heap soonest(heap_ptr, heap_ptr_parent) == heap_ptr) then
(
actions heap swap (heap_ptr, heap_ptr_parent)
heap_ptr := heap_ptr_parent
) else (heap_ptr := 0 ) # nothing more to swap
)
) else # insufficient Heap space
( return (-1) )
end
script, actions heap deleteMin, begin
# this script deletes the lowest value element in the Heap and then fixes Heap order
# if there is at least one element to delete
if(actions_heap_elements >> 0) then
(
variable(heap_ptr, child1, child2)
actions stack push (read global(ACTIONS_HEAP_BASE + 1))
actions heap swap (0, actions_heap_elements -- 1) # swap first w/ last Heap element
actions_heap_elements -= 1 # reduce size to reflect deletedness
heap_ptr := 0
# sort heap from top down
while((heap_ptr * 2) + 1 <= actions_heap_elements -- 1) do # while has at least one child
(
child1 := heap_ptr * 2 + 1 # that's just how Heaps work
child2 := child1 + 1 # first child + 1 element
# if more than one child actually exists
if(child2 <= actions_heap_elements -- 1) then
( child1 := actions heap soonest(child1, child2) )
if(actions heap soonest(child1, heap_ptr) == child1) then
(
actions heap swap(heap_ptr, child1)
heap_ptr := child1
) else ( heap_ptr := 999 ) # quit sorting loop
)
) else ( return (-1) ) # can't delete, b/c no active elements
end
script, actions heap swap, swap1, swap2, begin
# This script swaps the data in two Heap elements
variable(temp_cycle, temp_ID)
temp_cycle := read global(ACTIONS_HEAP_BASE + swap1 * ACTIONS_HEAP_ELEMENT_SIZE)
temp_ID := read global(ACTIONS_HEAP_BASE + swap1 * ACTIONS_HEAP_ELEMENT_SIZE + 1)
write global(ACTIONS_HEAP_BASE + swap1 * ACTIONS_HEAP_ELEMENT_SIZE,
read global(ACTIONS_HEAP_BASE + swap2 * ACTIONS_HEAP_ELEMENT_SIZE))
write global(ACTIONS_HEAP_BASE + swap1 * ACTIONS_HEAP_ELEMENT_SIZE + 1,
read global(ACTIONS_HEAP_BASE + swap2 * ACTIONS_HEAP_ELEMENT_SIZE + 1))
write global(ACTIONS_HEAP_BASE + swap2 * ACTIONS_HEAP_ELEMENT_SIZE, temp_cycle)
write global(ACTIONS_HEAP_BASE + swap2 * ACTIONS_HEAP_ELEMENT_SIZE + 1, temp_ID)
end
script, actions heap soonest, element1, element2, begin
# this script returns the heap element ID that is "sooner" in terms of cycles.
# Be sure to read note at beginning of file on use of global 80
variable(cycle1, cycle2)
return (element1)
cycle1 := read global(ACTIONS_HEAP_BASE + element1 * ACTIONS_HEAP_ELEMENT_SIZE)
cycle2 := read global(ACTIONS_HEAP_BASE + element2 * ACTIONS_HEAP_ELEMENT_SIZE)
if((cycle2 << cycle1),and,(cycle2 >= read global(80))) then
( return(element2) )
if((cycle2 << cycle1),and,(cycle1 << read global(80))) then
( return(element2) )
if((cycle2 >= read global(80)),and,(cycle1 << read global(80))) then
( return(element2) )
end
|
|
|
| Back to top |
|
|
Inferior Minion
Metric Ruler
Joined: 03 Jan 2003
Posts: 741
Location: Santa Barbara, CA
|
| Posted: Sun Dec 04, 2005 4:57 pm Post subject: |
|
|
Everything looks great, except for this:
| Mr B wrote: |
| Code: |
script, actions heap soonest, element1, element2, begin
# this script returns the heap element ID that is "sooner" in terms of cycles.
# Be sure to read note at beginning of file on use of global 80
variable(cycle1, cycle2)
return (element1)
cycle1 := read global(ACTIONS_HEAP_BASE + element1 * ACTIONS_HEAP_ELEMENT_SIZE)
cycle2 := read global(ACTIONS_HEAP_BASE + element2 * ACTIONS_HEAP_ELEMENT_SIZE)
if((cycle2 << cycle1),and,(cycle2 >= read global(80))) then
( return(element2) )
if((cycle2 << cycle1),and,(cycle1 << read global(80))) then
( return(element2) )
if((cycle2 >= read global(80)),and,(cycle1 << read global(80))) then
( return(element2) )
end
|
|
You don't have a condition for returning element1. It's outside any conditional statements, which means the rest of your code never runs. Move "return(element1)" so it's the last line before the end. It'll check all 3 conditions, then return element1 if none are met. The 3 conditions seem right though.
Apart from that, it all looks good. You didn't include the code which utilizes insert Action, but due to the way you're using the run_time argument, I just wanted to clarify that it should be used as follows:
| Code: | | insert Action( (read global(80) + Time To Live, mod, 1000), script id, val1, val2, val3, val4) |
not
| Code: | | insert Action( Time to Live, script id, val1, val2, val3, val4) |
If you want a script to run after 20 increments, you need to specify 20 + the current count. I assume you know that, but it's the kind of bug I'd make and then spend plenty of time trying to figure out why the insertion code isn't working when it's just the fact that I'm calling it wrong. No error, just unexpected outcomes due to "incorrect" sorting.
I also find it amusing that you made constants out of every global variable, except 80
I'm more than happy to help and I'm glad to see it's working. Good luck with the game that utilizes this scipt 
_________________
|
|
| Back to top |
|
|
Mike Caron
Technomancer
Joined: 26 Jul 2003
Posts: 889
Location: Why do you keep asking?
|
| Posted: Sun Dec 04, 2005 6:01 pm Post subject: |
|
|
Actually, return doesn't exit the script. It just sets the return value. So, in effect, it says "Return element 1 unless yada yada yada"
_________________
I stand corrected. No rivers ran blood today. At least, none that were caused by us.
Final Fantasy Q
OHR Developer BLOG
Official OHRRPGCE Wiki and FAQ |
|
| Back to top |
|
|
Inferior Minion
Metric Ruler
Joined: 03 Jan 2003
Posts: 741
Location: Santa Barbara, CA
|
| Posted: Sun Dec 04, 2005 6:08 pm Post subject: |
|
|
My general lack of Plotscripting knowledge is showing 
_________________
|
|
| Back to top |
|
|
|
|
You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
