Castle Paradox Forum Index Castle Paradox

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 
 Gamelist   Review List   Song List   All Journals   Site Stats   Search Gamelist   IRC Chat Room

Slice Arrays and Linked Lists
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Castle Paradox Forum Index -> The Arcade
View previous topic :: View next topic  
Author Message
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA




Joined: 19 Feb 2003
Posts: 518
Location: Halifax

PostPosted: Sun Oct 24, 2010 7:41 pm    Post subject: Slice Arrays and Linked Lists Reply with quote

Someone probably already posted something like this, but I can't haz care.

For those of you who (like me) want to use arrays, but don't want to wait for them to be implemented, here's some scripts I wrote this evening which use slices to store data in 1D arrays.

The syntax is maybe a little annoying, but they work (last I tried). The only catch is that you need to be careful that you "destroy" the arrays when you're done using them ... otherwise you'll probably have a horrible memory leak on your hands.

Arrays will be very useful for SandS. Zones also solve many of my problems. I'll be able to make some progress now.

Code:
#####################################
######  Use Slices as Arrays ########
#####################################

# SLICE ARRAY (also LINKED LIST ITEMS) SYNTAX:
# Creator:    arrayHandle := createArr(size)
# Destructor: destroyArr(arrayHandle)
# Mutators:   wArr(arrayHandle,index,value)
#             setNextArr(arrayHandle,nextHandle)
#             setPrevArr(arrayHandle,prevHandle)
# Readers:    rArr(arrayHandle,index)
#             arraySize := sizeOfArr(handle)
#             arrayHandle := nextArr(arrayHandle)
#             arrayHandle := prevArr(arrayHandle)

### Allocate a slice array and its size.
SCRIPT, createArr, size, BEGIN
  variable(arrSl)
  arrSl := CREATE CONTAINER
  variable(sizeDiv3)
  sizeDiv3 := size/3
 # Add the array's babies.
  variable(counter,baby)
  FOR(counter,1,sizeDiv3+1)DO(
    baby := CREATE CONTAINER
    SET PARENT(baby,arrSl)
  )
  SET SLICE EXTRA (arrSl,0,size)
 # Don't waste processing time drawing these slices
  SET SLICE VISIBLE (arrSl,off)
  EXIT RETURNING (arrSl)
END

### Write to the array
SCRIPT, wArr, handle,index,value, BEGIN
  SET SLICE EXTRA (SLICE CHILD (handle,index/3),modulus(index,3),value)
END

### Read from the array
SCRIPT, rArr, handle,index, BEGIN
  variable(returnVal)
  returnVal := GET SLICE EXTRA (SLICE CHILD (handle,index/3),modulus(index,3))
  EXIT RETURNING (returnVal)
END

### Get the array's size
SCRIPT, sizeOfArr, handle, BEGIN
  EXIT RETURNING(GET SLICE EXTRA (handle,0))
END

### List Item Accessors:
SCRIPT, prevArr, arr, BEGIN
  EXIT RETURNING ( GET SLICE EXTRA (arr,1) )
END
SCRIPT, nextArr, arr, BEGIN
  EXIT RETURNING ( GET SLICE EXTRA (arr,2) )
END

### List Item Mutators:
SCRIPT, setPrevArr, arr,prev, BEGIN
  SET SLICE EXTRA (arr,1,prev)
END
SCRIPT, setNextArr, arr,next, BEGIN
  SET SLICE EXTRA (arr,2,next)
END

### Destroy a slice array (and all its babies)
SCRIPT, destroyArr, handle, BEGIN
  FREE SLICE (handle)
END

_________________
Working on rain and cloud formation


Last edited by Bagne on Mon Oct 25, 2010 5:27 pm; edited 3 times in total
Back to top
View user's profile Send private message
TMC
On the Verge of Insanity




Joined: 05 Apr 2003
Posts: 3228
Location: Matakana

PostPosted: Sun Oct 24, 2010 9:06 pm    Post subject: Reply with quote

Heh, I hadn't thought of storing data three to a slice. No array resizing?

Ah, someone who realises that the mod operator is just too likely to cause grief and should be avoided. I wish I realised that :(
_________________
"It is so great it is insanely great."
Back to top
View user's profile Send private message Send e-mail MSN Messenger
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA




Joined: 19 Feb 2003
Posts: 518
Location: Halifax

PostPosted: Mon Oct 25, 2010 4:11 am    Post subject: Reply with quote

What are the limits to slice use? How many can co-exist?
Is there any slowdown if they're all invisible?
Do slice values get stored in save files?

Quote:
... three to a slice

I got mouths to feed!

Quote:
array resizing

I'm trying to keep make my life simple :-)
Also, I don't want to keep these scripts—I'm hoping to replace them with legit hspeak when arrays are available ... but maybe I'm incorrect when I assume that hspeak array resizing will not be an option.

Quote:
mod operator

all those commas ...
_________________
Working on rain and cloud formation
Back to top
View user's profile Send private message
TMC
On the Verge of Insanity




Joined: 05 Apr 2003
Posts: 3228
Location: Matakana

PostPosted: Mon Oct 25, 2010 4:25 am    Post subject: Reply with quote

Bagne wrote:
What are the limits to slice use? How many can co-exist?
Unlimited.

Bagne wrote:
Is there any slowdown if they're all invisible?
No, unless you have bajillions of invisible slices parented to a visible slice. Having bajillions of slices will also make creating new slices slower. I think your biggest problem would be that child slices are stored in a linked list, so accessing the 10000th element of your array could be a little slow.

Bagne wrote:
Do slice values get stored in save files?
Coming soon! Actually, we already agreed to start adding new data to RSAV, so I guess there's nothing stopping anyone from adding this immediately...

Bagne wrote:
but maybe I'm incorrect when I assume that hspeak array resizing will not be an option.
Huh?
_________________
"It is so great it is insanely great."
Back to top
View user's profile Send private message Send e-mail MSN Messenger
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA




Joined: 19 Feb 2003
Posts: 518
Location: Halifax

PostPosted: Mon Oct 25, 2010 4:47 am    Post subject: Reply with quote

Ever wonder how big a bajillion is?
Well, it's probably bigger than this:
http://www.vendian.org/envelope/dir2/lots_of_dots/million_dots.html

TMC wrote:

Bagne wrote:
but maybe I'm incorrect when I assume that hspeak array resizing will not be an option.
Huh?

That's my confusing way of saying that I didn't know what features will be available for the new hspeak arrays.

Cool.
Thanks for the info.
_________________
Working on rain and cloud formation
Back to top
View user's profile Send private message
Bob the Hamster
OHRRPGCE Developer




Joined: 22 Feb 2003
Posts: 2525
Location: Hamster Republic (Southern California Enclave)

PostPosted: Mon Oct 25, 2010 7:18 am    Post subject: Reply with quote

Bagne wrote:

Quote:
... three to a slice

I got mouths to feed!


Why just three? In Don't Eat Soap and bell of Chaos I cram in 11 integers per slice

extra 0
extra 1
extra 2
x
y
width
height
top padding
right padding
bottom padding
left padding

All those other values have the same legal range as the "extra" values do, and since the slices are children of an invisible parent, none of those numbers mean anything else.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA




Joined: 19 Feb 2003
Posts: 518
Location: Halifax

PostPosted: Mon Oct 25, 2010 8:12 am    Post subject: Reply with quote

Oo.

That didn't occur to me. Do all values store the same datatype?
Are any of them bounded? Like ... padding can't be larger than width or something?
_________________
Working on rain and cloud formation
Back to top
View user's profile Send private message
TMC
On the Verge of Insanity




Joined: 05 Apr 2003
Posts: 3228
Location: Matakana

PostPosted: Mon Oct 25, 2010 9:11 am    Post subject: Reply with quote

James Paige wrote:
All those other values have the same legal range as the "extra" values do


That means yes.


Well, a million is probably a bit bigger than the "bajillion" I imagined. A million slices would take about 160MB of memory and would slow slice creation functions to a crawl.

We'll definitely have resizeable arrays. Strangely I have not actually considered the syntax for resizing them yet.
_________________
"It is so great it is insanely great."
Back to top
View user's profile Send private message Send e-mail MSN Messenger
Bob the Hamster
OHRRPGCE Developer




Joined: 22 Feb 2003
Posts: 2525
Location: Hamster Republic (Southern California Enclave)

PostPosted: Mon Oct 25, 2010 9:51 am    Post subject: Reply with quote

Bagne wrote:
Oo.

That didn't occur to me. Do all values store the same datatype?
Are any of them bounded? Like ... padding can't be larger than width or something?


Nope. no bounding on any of them.

The Mad Cacti wrote:
We'll definitely have resizeable arrays. Strangely I have not actually considered the syntax for resizing them yet.


My wishlist for array length manipulation:

* append
* insert
* delete
* pop (which would compliment append's "push")

I could care less whether or not we end up with anything resembling FreeBasic's REDIM. I don't actually see myself using that in a real game.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Newbie_Power




Joined: 04 Sep 2006
Posts: 1762

PostPosted: Mon Oct 25, 2010 12:00 pm    Post subject: Reply with quote

Everytime I suggest using Slices as a substitute for arrays, people always moan and complain to me about why they wish arrays would come soon.
_________________

TheGiz> Am I the only one who likes to imagine that Elijah Wood's character in Back to the Future 2, the kid at the Wild Gunman machine in the Cafe 80's, is some future descendant of the AVGN?
Back to top
View user's profile Send private message
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA




Joined: 19 Feb 2003
Posts: 518
Location: Halifax

PostPosted: Mon Oct 25, 2010 5:23 pm    Post subject: Reply with quote

Hey doods.
I wanted to store lists of stuff. So here I'm storing linked lists of slice arrays. If I write and access the arrays according to a particular format, I can start treating them like objects.

I'll soon be ready to create and destroy clouds.
Clouds! Hoha!

Oh, and my array code had a bug in it. I edited the OP, so it's now fixed.

Code:

# SLICE ARRAY (also LINKED LIST ITEMS) SYNTAX:
# Creator:    arrayHandle := createArr(size)
# Destructor: destroyArr(arrayHandle)
# Mutators:   wArr(arrayHandle,index,value)
#             setNextArr(arrayHandle,nextHandle)
#             setPrevArr(arrayHandle,prevHandle)
# Readers:    rArr(arrayHandle,index)
#             arraySize := sizeOfArr(handle)
#             arrayHandle := nextArr(arrayHandle)
#             arrayHandle := prevArr(arrayHandle)
# LINKED LIST SYNTAX:
# List Creator:    linkedList := createLL
# List Destructor: destroyLL(linkedList)
# List Mutators:   addEndLL(linkedList,arrayHandle)
#                  addFrontLL(linkedList,arrayHandle)
#                  delEndLL(linkedList)
#                  delFrontLL(linkedList) 
# List Readers:    arrayHandle := endOfLL(linkedList)
#                  arrayHandle := frontOfLL(linkedList)
#                  sizeOfLL(linkedList)



#######################################
######  Linked Lists of Arrays ########
#######################################

### Linked list accessors:
SCRIPT, sizeOfLL, LL, BEGIN
  EXIT RETURNING( GET SLICE EXTRA (LL,0) )
END
SCRIPT, frontOfLL, LL, BEGIN
  EXIT RETURNING( GET SLICE EXTRA (LL,1) )
END
SCRIPT, endOfLL, LL, BEGIN
  EXIT RETURNING( GET SLICE EXTRA (LL,2) )
END

### List Item Accessors:
SCRIPT, prevArr, arr, BEGIN
  EXIT RETURNING ( GET SLICE EXTRA (arr,1) )
END
SCRIPT, nextArr, arr, BEGIN
  EXIT RETURNING ( GET SLICE EXTRA (arr,2) )
END

### List Item Mutators:
SCRIPT, setPrevArr, arr,prev, BEGIN
  SET SLICE EXTRA (arr,1,prev)
END
SCRIPT, setNextArr, arr,next, BEGIN
  SET SLICE EXTRA (arr,2,next)
END


### Create a Linked List
SCRIPT, createLL, BEGIN
  variable(LL)
  LL := CREATE CONTAINER # Allocate space for linked list
  setSizeOfLL(LL,0)   # size zero
  setFrontOfLL(LL,-1) # NULL pointer to "first" item on list
  setEndOfLL(LL,-1)  # NULL pointer to "last" item on list
  EXIT RETURNING (LL) # Return the LL pointer
END

### Add a slice array to the end of a linked list
SCRIPT, addEndLL, LL,newArr, BEGIN
  variable(sizeOfList,frontOfList,endOfList)
  sizeOfList := sizeOfLL(LL)
  frontOfList := frontOfLL(LL)
  endOfList := endOfLL(LL)
 
  # Set pointers on newArr
  setPrevArr(newArr,endOfList) # set newArr's "prev" pointer as endOfList
  setNextArr(newArr,-1)        # set newArr's "next" pointer as NULL
 
  # Set endOfList's "next" pointer, or if list is empty, set LL's "first" pointer
  IF(sizeOfList <> 0) THEN(
    # Error check: arrays in list must be of equal size
    IF (sizeOfArr(newArr) <> sizeOfArr(endOfList)) THEN(
      cryError (-31415926)
    )
    setnextArr(endOfList,newArr) # set endOfList's "next" pointer as newArr
  )
  ELSE(
    setfrontOfLL(LL,newArr)          # set LL's "first" pointer as newArr
  )
 
  # Final assignments on LL.
  setSizeOfLL(LL,sizeOfList+1)   # Increment list size
  setendOfLL(LL,newArr)         # set LL's "last" pointer as newArr
END

### Add a slice array to the end of a linked list
SCRIPT, addFrontLL, LL,newArr, BEGIN
  variable(sizeOfList,frontOfList,endOfList)
  sizeOfList := sizeOfLL(LL)
  frontOfList := frontOfLL(LL)
  endOfList := endOfLL(LL)
 
  # Set pointers on newArr
  setnextArr(newArr,frontOfList) # set newArr's "next" pointer as frontOfList
  setprevArr(newArr,-1)          # set newArr's "prev" pointer as NULL
 
  # Set "prev" pointer on frontOfList, or if list is empty, set LL's "last" pointer
  IF(sizeOfList <> 0) THEN(
    # Error check: arrays in list must be of equal size
    IF (sizeOfArr(newArr) <> sizeOfArr(endOfList)) THEN(
      cryError (-31415926)
    )
    setprevArr(frontOfList,newArr) # set frontOfList's "prev" pointer as newArr
  )
  ELSE(
    setendOfLL(LL,newArr)          # set LL's "last" pointer as newArr
  )
 
  # Final assignments on LL.
  setSizeOfLL(LL,sizeOfList+1)   # Increment list size
  setfrontOfLL(LL,newArr)         # set LL's "first" pointer as newArr
END

### Delete the last slice array on a linked list
SCRIPT, delEndLL, LL, BEGIN
  variable(sizeOfList,frontOfList,endOfList)
  sizeOfList := sizeOfLL(LL)
  frontOfList := frontOfLL(LL)
  endOfList := endOfLL(LL)
  # Error check:  Can't delete stuff if it's empty
  IF(sizeOfList == 0) THEN(
    cryError(-31415927)
  )
  variable(newendOfList)
  newendOfList := prevArr(endOfList)
  setNextArr(newendOfList,-1)
  destroyArr(endOfList)
  setEndOfLL(LL,newendOfList)
  setSizeOfLL(LL,sizeOfList -- 1)
END

### Delete the first slice array on a linked list
SCRIPT, delFrontLL, LL, BEGIN
  variable(sizeOfList,frontOfList,endOfList)
  sizeOfList := sizeOfLL(LL)
  frontOfList := frontOfLL(LL)
  endOfList := endOfLL(LL)
  # Error check:  Can't delete stuff if it's empty
  IF(sizeOfList == 0) THEN(
    cryError(-31415927)
  )
  variable(newfrontOfList)
  newfrontOfList := nextArr(frontOfList)
  setPrevArr(newfrontOfList,-1)
  destroyArr(frontOfList)
  setFrontOfLL(LL,newfrontOfList)
  setSizeOfLL(LL,sizeOfList -- 1)
END

SCRIPT, destroyLL, LL, BEGIN
  variable(current, next)
  current := frontOfLL(LL)
  WHILE(current<>-1)DO(
    next := nextArr(current)
    destroyArr(current)
    current := next
  )
  FREE SLICE (LL)
END


### Linked list mutators (These are helpers. DON'T USE DIRECTLY):
SCRIPT, setSizeOfLL, LL,size, BEGIN
  SET SLICE EXTRA (LL,0,size)
END
SCRIPT, setFrontOfLL, LL,first, BEGIN
  SET SLICE EXTRA (LL,1,first)
END
SCRIPT, setEndOfLL, LL,last, BEGIN
  SET SLICE EXTRA (LL,2,last) 
END

SCRIPT, cryError, arg, BEGIN
  SHOW VALUE (arg)
  WAIT(20)
  WAIT FOR KEY (any key)
  GAME OVER
END

_________________
Working on rain and cloud formation
Back to top
View user's profile Send private message
TMC
On the Verge of Insanity




Joined: 05 Apr 2003
Posts: 3228
Location: Matakana

PostPosted: Thu Oct 28, 2010 9:29 am    Post subject: Reply with quote

Wow, that's neat Bagne, but... what's the point of reimplementing lists? The difference between lists and arrays is just an internal implementation detail, and slices are already stored in lists. If you don't 'splice' your lists (eg. splitting off the first 5 elements, which there's no slice command for), then you could just parent all your arrays to a slice and use 'slicetofront' to append to the front.

James Paige wrote:
I could care less whether or not we end up with anything resembling FreeBasic's REDIM. I don't actually see myself using that in a real game.


Splicing an array (to shorten it) plus being able to extend an array by pushing n copies of something covers all uses of REDIM.
_________________
"It is so great it is insanely great."
Back to top
View user's profile Send private message Send e-mail MSN Messenger
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA




Joined: 19 Feb 2003
Posts: 518
Location: Halifax

PostPosted: Thu Oct 28, 2010 4:09 pm    Post subject: Reply with quote

Touché.
No need to re-invent the wheel.
Oh well, it was good practice.

I might switch to the conventional slice commands, but keep my syntax- I would prefer to reserve commands with "slice" in the name for doing actual graphical stuff, and stuff with "list" in the name for data management.

Wait ... what would be the command for un-parenting something without destroying it? Do you just parent it to the map or something?
_________________
Working on rain and cloud formation
Back to top
View user's profile Send private message
TMC
On the Verge of Insanity




Joined: 05 Apr 2003
Posts: 3228
Location: Matakana

PostPosted: Thu Oct 28, 2010 5:24 pm    Post subject: Reply with quote

Yes, just parent it elsewhere.
_________________
"It is so great it is insanely great."
Back to top
View user's profile Send private message Send e-mail MSN Messenger
Bagne
ALL YOUR NUDIBRANCH ARE BELONG TO GASTROPODA




Joined: 19 Feb 2003
Posts: 518
Location: Halifax

PostPosted: Fri Nov 12, 2010 11:20 am    Post subject: Reply with quote

James Paige wrote:

11 integers per slice:
extra 0
extra 1
extra 2
x
y
width
height
top padding
right padding
bottom padding
left padding

Done.
Making some 2-d arrays now. Don't really feel the need to generalize to n-d arrays.

Should have asked this earlier ... has any decision been made on the indexing of future arrays?
Will the first slot be index 0 or index 1?
I just want to convert my own arrays to the same index system so that when real ones come, it will be easier to make the transition.
_________________
Working on rain and cloud formation
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Castle Paradox Forum Index -> The Arcade All times are GMT - 8 Hours
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot 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