Yesterday I took again a little bit time and changed the sources.
I added a first “weird” explosion type of thing – but that is about the only thing that is visible for the user :-).
I had a brief email chat with Thomas and he suggested, that I should organize my object list differently. While I never was quite comfi with the way I first implemented it (counter + structures), and I even had thoughts about linked lists before – I needed a little push to actually come around and implement it.
In simple terms, the way the objects were structured befor:
MAX_OBJECT equ 20 struct Object data1 ds,2 data2 ds,2 ... data3 ds,2 end struct org $c880 ObjectList ds Object*MAX_OBJECT objectlist_count ds 1 ...
You get my meaning. I reserved space for the object list, remembered how many objects were used and upon usage incremented the count.
When I removed an object, than the space in the list would be “cleaned” and another (usually the last) object took its place. So all objects were always counted from the start and all were sorted.
Adding a new object required a MUL:
lda spawn_count ldb #ObjectStruct mul ldx #object_list ; object list leax d,x ; pointer to new object ...
Removing an object was also “stressfull”:
; in x the current object list pos removeObject: dec spawn_count ; get last object and fill the just "freed" space beq do_done ; if it was the last object, we do not need to copy anything ; load u pointer with last pos pshs x leax ,u ; moveMem TO lda spawn_count ldb #ObjectStruct mul ldu #object_list ; object list leau d,u ; moveMem FROM ; now copy all entries lda #ObjectStruct ; moveMem count jsr Move_Mem_a leau ,x ; restore old u puls x rts
And going thru all objects to draw/handle them was done in a loop:
do_objects lda spawn_count sta tmp_count ldu #object_list do_next: dec tmp_count bmi do_done ; object lists are nicely ordered, so we start at the beginning ... bra do_next do_done: rts
While this certainly works well – using a different data model and a little bit of “object oriented” thinking (and the usage of the user stack) – led to a slightly different implementation.
Mainly two changes were done:
a) DATA STRUCTURE as a list
the object data is now kept in a linked list, the data structure itself now contains a next and previous element (although, if I need more RAM later on, I might drop the “previous”)
b) DATA vs OBJECT
the data now is more than just data, it is actually OBJECT information, not only data. The structure now contains pointers to functions
which leads to
c) COMBINING those with user stack usage – is cool!
Ok, more information.
DATA STRUCTURE
The data of all objects in the basic structure looks (at the moment) like:
(the actual order of the items might be changed when I use even more user stacking)
struct ObjectStruct ds BEHAVIOUR,2 ds TYPE,1 ; enemy type ds SCALE,1 ; scale to position the object ds ANGLE,2 ; if angle base, angle in degree *2 ds Y_POS,1 ; current position ds X_POS,1 ds CURRENT_LIST,2 ; current list vectorlist ds DRAW_ROUTINE,2 ; jmp to current draw routine ds PREVIOUS_OBJECT,2 ; positive = start of list ds NEXT_OBJECT,2 ; positive = end of list ds filler, 5 end struct
That structure has definitions used by all objects. In an object oriented manner speaking, that class is a parent to other classes which will ‘inherit’ the above given definitions.
The “filler” section will contain additional used data (by child classes) which is arbitrary e.g.:
struct XObjectStruct ds BEHAVIOUR,2 ds TYPE,1 ; enemy type ds SCALE,1 ; scale to position the object ds ANGLE,2 ; if angle base, angle in degree *2 ds Y_POS,1 ; current position ds X_POS,1 ds CURRENT_LIST,2 ; current list vectorlist ds DRAW_ROUTINE,2 ; jmp to current draw routine ds PREVIOUS_OBJECT,2 ; positive = start of list ds NEXT_OBJECT,2 ; positive = end of list ds TICK_COUNTER,1 ; after how many rounds the movement updates (0 = each, 1 = every second etc) ds SPEED_COUNTER,1 ; with what value does the movement get updated (1-4)? ds ANIM_COUNTER,1 ; ds ORIGIN,2 ; pointer to original object definition ds filler, 0 end struct
Only two things are important:
- The structures must have the same length
- Fields with the same name must have the same “position” within the structure
The linked list of those objects is realized by two pointers
list_empty_head ds 2 ; if empty these contain a positive value that points to a RTS list_objects_head ds 2 ; if negative, than this is a pointer to a RAM location list_objects_tail ds 2
The empty list is initialized at cartridge start with “MAX_OBJECT” count elements (with next and previous elements set).
When I need a new object, I take the first one of the empty list and put it at the tail of my used list.
If I ‘delete’ an object from my list – I move the entry to the start of my empty list, and clean up the positions previous and next entries.
(and in both cases fix the previous and next elements – but if all cases are considered correctly this is straight forward)
DATA vs OBJECT
As seen in the above structure definition, there are (at least) two entries which are pointers to functions (methods in OO terminology).
These methods are:
– behaviour()
which controls what the object does (movement, collision, giving birth to other objects (shots…) etc)
each object type can have a different behaviour routine
– draw_routine()
how the object is drawn. Objects may be drawn differently (vector list with modes, normal vectorlist, list of dots etc)
Calling these methods thru the object data (at this point I would like to call it “class”) definitions allows to use the same calling conventions for all objects without any further further expansive CMP, TST or whatever statements. Yes, doing a indirect jump also costs cycles, but
a) all in all it is still cheaper if you have a couple of different objects
b) using a user stack it still gets cheaper
COMBINING
the data structure with the linked list and a behaviour “pattern” (my aren’t we using buzzwords today – btw did I mention, that my diploma theses was about design patterns?) following implementation is currently “active”:
Main loop:
main: jsr Wait_Recal ... do shield stuff jsr Reset0Ref jsr drawPlayerHome jsr Reset0Ref bsr check_spawn bsr do_objects bra main ; and repeat forever
The “interesting” do_objects function looks like:
do_objects ldu list_objects_head pulu pc
Yes, that realy is all!
The head of the list contains the first object structure, the objects structures first element is the behaviour method.
Within the behaviour method, the object does its own stuff and also calls its own draw routine (from the class definition). At the end of each behaviour following two lines are executed:
... ldu NEXT_OBJECT+u_offset1,u pulu pc
(with u_offset1 being the offset between the current U register and the structure start of the object definition).
Keeping in mind, that the start and the end of the list is an “empty” object structure that contains an object with its behaviour routine set to a single RTS – that behaviour pattern loops AUTOMATICALLY through all active objects without a single compare!
(Also – upon adding and removing entries a compare is necessary, but that is also easy when using 2 complement compares, the empty object structure is located in the cartridge ROM, which is positive, the object structures of the game objects are kept in a RAM memory location, which is negative – and thus can be easily compared using BPL or BMI).
(At some point I might chose to not use a subroutine do_objects() at all, and change the empty routine to a “JMP someplace” – or set it to the actual system stack, that way the RTS itself is automatically executed WITHOUT an rts instruction 🙂 )
Also changing one object type to another is in general quite easy, following routine changes a X object to an explosion:
; exchange the object structure pointed to by U register ; with a new "explosion" type object exchangeToExplosion: lda #TYPE_EX sta TYPE, u ldd #explosionBehaviour std BEHAVIOUR,u clr EXPLOSION_SCALE,u ldd #explosionDotDraw std DRAW_ROUTINE,u rts
The position and angle information (and the whole object structure) is reused.
(in the words of yet another computer language, the structure is actually used as a UNION and the positions are reused with different values and meanings – in this case the “TICK_COUNTER” is used now as an “EXPLOSION_SCALE”).
I hope I did not confuse you all to much with my ramblings. For the show a slightly modified image from last time… featuring a set of explosions :-).
yep i was confused but those pics look ace 🙂
Hehe – thx – I think…
So, you created “SmartObjects”.
// At some point I might chose to not use a subroutine do_objects() at all…
VecForth’s whole “dictionary” of subroutines is in a linked list. When you compile or run a new “word” i.e. subroutine, Forth traverses the linked list to find if it exists, and compiles the address of the word or executes the code at that address. When compiled, there is basically a list of addresses that make up your program and each one updates the Y register to be the address of the next piece of code to run. It doesn’t use any jsr/rts, everything is a jmp [,y++], which is faster and smaller. (To confuse things more, VecForth uses the S stack for parameters and U stack for return addresses, loop counters etc., but that’s another story.)
There are some optimizations possible (though probably not relevant for your usage):
– When reading an item from the linked list, you can also move it to the start of list, so you generally end up with a fast search on items that are searched for most often.
– Use multiple linked-lists based on a specific parameter of the objects e.g. first character of the name/identifier.
Alternatively, Forth can use a hash table for fastest lookup in constant’ish time, but for runtime speed you need lots of memory, so that’s probably not feasible for Vectrex, unless it’s a static set of data in ROM.
Either way, linked-lists are pretty useful, bearing in mind their simplicity!