I cannot believe I did not think of this earlier

Error message

Deprecated function: implode(): Passing glue string after array is deprecated. Swap the parameters in drupal_get_feeds() (line 394 of /var/www/pied-piper.ermarian.net/includes/common.inc).

Author	Topic: I cannot believe I did not think of this earlier
Walker White Apprentice Member # 4127	written Wednesday, April 7 2004 11:08 Profile #0 I must be slipping in my old age. While writing my scripts I have been periodically lamenting the lack of arrays and dynamic structures. And then it hit me. The SDFs are heap space. Persistent heap space that is saved when you quit the game (so long as you saved). We can make arrays, linked lists, binary trees, and whatever we want here. And you can use memory cells as pointers. Of course, every space used as the heap takes away from legitimate use in the story line, which is very uncool. And there are only 300 x 30 = 9000 spaces, so that starts to make it look a little tight. If only Jeff had given us more SDFs. Of course I am not expecting full 32 bit addressing (as the SDFs are indexed by two 16 bit shorts). But he could have given us 16 bit addressing (256 x 256). That ups the number of nodes to 64k and Blades of Avernum becomes the equivalent of a C64. And the save file cannot be that much larger from it, can it? Posts: 48 \| Registered: Saturday, March 20 2004 08:00
Banana Apprentice Member # 412	written Wednesday, April 7 2004 18:00 Profile #1 The 9k limitation is certainly annoying if you want to use this trick for persistent data structures, but it's not a problem for pseudo-stack arrays. We could just set aside a range of, say, 1000 SDFs as the 'array area' and reuse it as necessary. Of course, you'd need to make sure to initialise it every use, which could get slow. Posts: 33 \| Registered: Monday, December 17 2001 08:00
spyderbytes Shock Trooper Member # 4180	written Wednesday, April 7 2004 18:51 Profile #2 Hmmm... yeah, I'd think initialization would become QUITE expensive, especially considering the modest system requirements for the game (any Mac running 8.1 covers a lot of ground, meaning it's going to be running on a fair number of, face it, obsolete boxes). Still, it's worth bearing in mind for situations where nothing else will do. :) -spyderbytes -------------------- -spyderbytes Posts: 200 \| Registered: Wednesday, March 31 2004 08:00
Drakefyre Triad Mage Member # 7	written Thursday, April 8 2004 01:10 Profile Homepage #3 A stack would not be hard to implement at all, and neither would a normal array or an array-based implementation of binary trees. I think you're asking for a bit much with linked lists. It's also certainly possible to develop a hashing method that would be limited to a set of SDFs that's not being used for actual SDF purposes. -------------------- "At times discretion should be thrown aside, and with the foolish we should play the fool." - Menander ==== Drakefyre's Demesne - Happy Happy Joy Joy Encyclopedia Ermariana - Trapped in the Closet ==== You can take my Mac when you pry my cold, dead fingers off the mouse! Posts: 9436 \| Registered: Wednesday, September 19 2001 07:00
Banana Apprentice Member # 412	written Thursday, April 8 2004 04:48 Profile #4 Linked lists are not hard at all. Here's an implementation: http://banana.ucc.asn.au/t0NewTown.txt Drop it in as a town script and watch the console output when the party enters. Notes: This implementation pretends that SDFs are a flat address space by using / and %. For example, SDF "8000" -> (8000/30,8000%30) -> (266,20). The only issue with using SDFs as pointers to SDFs is that they are 1 byte rather than two, so I've encoded pointers across two SDFs with a naive algorithm: bitshift one of them left 8 by multiplying by 256. The overhead is therefore 2 bytes per link node. Unfortunately, given a 9 KB address space, this is not insignificant. A tree or other multiply linked structure would be trivial Posts: 33 \| Registered: Monday, December 17 2001 08:00
Walker White Apprentice Member # 4127	written Thursday, April 8 2004 05:00 Profile #5 Circular queues turn out to be quite efficient in the SDFs when you are willing to allow a buffer limit. Last night I figured out how to use them to reintroduce area effect spells (with delayed effect even) into the game with an event queue. Unfortunately, work is picking up again, so you all will have to wait a week or two for those scripts. Posts: 48 \| Registered: Saturday, March 20 2004 08:00
Walker White Apprentice Member # 4127	written Thursday, April 8 2004 05:22 Profile #6 quote: Originally written by Banana: We could just set aside a range of, say, 1000 SDFs as the 'array area' and reuse it as necessary. Of course, you'd need to make sure to initialise it every use, which could get slow. I am thinking of using y values 27, 28, and 29 as heap space in my scripts. This can be used for arrays, queues, whatever. This gives us 900 bytes and still leaves over 8k for story. Someone who is actually writing adventures (Drake? TM?) should comment on whether this is acceptible; I am just script support right now (Think of me as a magic item artificer). As for initialization, I think this depends on whether you want a formal allocation system in the scenario script. Right now, I am inclined just to have scripts manually carve out their own space. To have a real allocation system we would probably need the following: A pointer to the next free memory location.A stack to keep track of what memory is in use.The ability to garbage collect occasionally. As linked lists require two nodes per pointer, Stop and Copy is probably the most efficient here. However, that leaves half the memory unused at any give time.As you see, this gets really expensive for <1k. As I said in the beginning, oh what we couldn't do with 64k. Posts: 48 \| Registered: Saturday, March 20 2004 08:00
Walker White Apprentice Member # 4127	written Thursday, April 8 2004 06:24 Profile #7 quote: Originally written by Banana: We could just set aside a range of, say, 1000 SDFs as the 'array area' and reuse it as necessary. Of course, you'd need to make sure to initialise it every use, which could get slow. It just occurred to me that I thought you were suggesting one thing, when you were really suggesting another. Are you suggesting arrays that only persist within a single state and need to be reinitialized each time the state is called? Because yes, we can do that, but you are right in saying that it is expensive. Even my G4 400 would probably not like that. Anything else you must be much more careful with, because we are looking at a class OS shared resource problem here. Each script is a thread. That's why I think these sorts of tricks should be avoided in terrain and creature scripts (which have memory cells anyway). Posts: 48 \| Registered: Saturday, March 20 2004 08:00
Banana Apprentice Member # 412	written Thursday, April 8 2004 07:06 Profile #8 quote: Originally written by Walker White: Are you suggesting arrays that only persist within a single state and need to be reinitialized each time the state is called? No, I just wasn't thinking properly when I made the post. It doesn't matter that the SDF-heap is persistent, as long as different scripts don't clobber different parts of it. Space vs time tradeoffs.. it's just like Embedded Systems 204 all over again :) I agree that a real malloc system would be unnecessarily messy. It would necessitate something like your states-as-functions hack, too. Incidentally, I do that slightly differently - I've been playing with having a set of globals like this in every script: and setting up a proper calling convention - caller's responsibility to save stack, callee's to return properly. I have state constants along the lines of and use set_state_continue(s0 / 10); to return or jump around. This allows for granularity within states without having to swap memory cells around or massively overload return_offset, but it does turn some states into a mass of I'm thinking of writing a set of m4 macros (or a "compiler") to turn all this out given c-like functions as input :) Posts: 33 \| Registered: Monday, December 17 2001 08:00
Walker White Apprentice Member # 4127	written Thursday, April 8 2004 07:27 Profile #9 quote: Originally written by Banana: This allows for granularity within states without having to swap memory cells around or massively overload return_offset, but it does turn some states into a mass of I'm thinking of writing a set of m4 macros (or a "compiler") to turn all this out given c-like functions as input :) Yeah. I have known you can do that for some time, but I am trying to keep overhead down some. The hack in AdvancedNPC works only because the function calls are in an initial loop. You are suggesting to turn the states into basic code blocks (that's the compiler terminology) around a function call. This necessitates breaking up branches and loops if there are function calls in them. What you are suggesting is the clean and proper way, it just causes state explosion. At that point it becomes an exercise in "What can AvernumScript do?". Which can be fun (that's certainly the game I have been playing), but we should always temper this with providing helpful stuff to the community here. If we write convoluted scripts that they cannot understand or at least customize through memory cells, then it won't be too useful. Posts: 48 \| Registered: Saturday, March 20 2004 08:00
Drakefyre Triad Mage Member # 7	written Friday, April 9 2004 01:40 Profile Homepage #10 I think that it would be fine if you took the whole range of SDFs from 250,0 upwards. Using the end y-values from earlier x-values is generally not a good idea, especially in some towns. -------------------- "At times discretion should be thrown aside, and with the foolish we should play the fool." - Menander ==== Drakefyre's Demesne - Happy Happy Joy Joy Encyclopedia Ermariana - Trapped in the Closet ==== You can take my Mac when you pry my cold, dead fingers off the mouse! Posts: 9436 \| Registered: Wednesday, September 19 2001 07:00