28th of November – Collision detection

As mentioned in my last post – “der Luchs” is (re-) programming his game “Menschenjagd”.

We met at an event last month and came to talk to each other. One thing led to another and he asked my opinion about it – and me not being shy – told it :-).

Sascha does not think of himself of being a “programmer” – inspite of him releasing game after game on various platforms (including more than 10 games for the vectrex). He keeps saying “I am an musician – not a programmer” – that might be one of the reasons he is a bit shy about showing (or sharing) his source code with other people. (Let me tell you: On many different levels – “I have seen much worse! -Nothing to be ashamed of!”)

On the other hand – I myself always liked “opening my sources” for two reasons:

a) so others can profit from the time I invested

b) so I can profit when others discover flaws in my programming

Actually so far mainly bullet point a) seems to work out the way as intended. And that does NOT mean that I don’t produce flaws – but I think people (in general) don’t care about giving much feedback.

Anyway. I would like to ask your opinion about our thoughts about the way the player/enemies/shots “navigate” the labyrinth in Menschenjagd.

First – although I programmed a lot vectrex stuff – for many assembler years I have not used many (if at all) BIOS routines – so using BIOS was not natural to me anymore (getting Obj_Hit to work needed some surfing 🙂 ).

Challenge Labyrinth – how to navigate?

In the upper playfield the player (and the enemies) are located in a labyrinth. Naturally the walls of the labyrinth should prevent the player (and the enemy) from just passing thru. Trying out the most obvious thing first – collision detection using Obj_hit of the Vectrex BIOS.

(For hints to the usage:
Manus source codes in particular coleman.as9 – collision detection routine with wise input included from Alex Herbert: Alex explains Obj_Hit (rec.games.vectrex))

For that particular collision detection, each wall segment was treated as an object and each player as another object. If a collision was immanent – than the move was not allowed.

In order for this to work, all labyrinth segements had to be tested against all players (I summarize under the term “player” also the enemies from now on). This actually did work – but needless to say – this was quite time consuming – and for various reasons (which I am not going into) – to slow.

In the following I am trying to explain with my own words the labyrinth test we came up with. Comments – especially more performant suggestions are as always welcome.

We divided the labyrinth into “tiles”, like the following (badly drawn) picture shows:

The following two assumptions are made:

1) Players can only move on the red lines. Players can only change direction on nodes of those lines.

2) Each rectangle inclosed in red lines is a tile. A tile like in a board game (e.g. “Carcassone”) and on each tile walls are painted. Walls from the center to the edge of the tile. The walls block player passages.

E.g. the uppermost left tile:  shows two walls one from the center to right, and one from the center to he bottom of the tile. etc…

A player that is located on a node of the red lines can only go to a direction where both neighboring tiles have no corssesponding wall sections (this will later be reduced to a check for just one tile – we assume the labyrinth is build correctly).

Example – this image:

The player resides on the crossing. He is allowed to go right – since both tiles on the right have no walls barring his way  (the upper tile has no wall from center to bottom, and the lower tile no wall from the center to the top).

Naturaly (as said) the labyrinth must be drawn with “correct” tiles in mind – without creating any contradictions.

Since one can’t very well use tiles as “data” to test against, we decided to abstract the image of the walls and represent each possible tile as a BYTE in memory.  The lower 4 bits of the byte represents the state of a wall present (or not).

A wall from center to the top will be represented by the presence (or absence) of bit 0. Thus 0001 represents a wall from center to top and 0000 represents NO wall from center to top.

A wall from center to the bottom will be represented by the presence (or absence) of bit 1. Thus 0010 represents a wall from center to bottom and 0000 represents NO wall from center to bottom.

 etc.

Bit 2 represents right, bit 3 represents left.
Doing that we created a 4 bit value for each possible permutation of walls.

(16 possible different tiles).

The first row of above labyrinth is then represented as:
db 0b0110 ; 1. positions right and bottom have a wall
db 0b1100 ; 2. positions right and left have a wall
db 0b1100 ; 3. positions right and left have a wall
db 0b1110 ; 7. positions right and left and bottom have a wall
db 0b1100 ; 5. positions right and left have a wall
db 0b1100 ; 6. positions right and left have a wall
db 0b1110 ; 7. positions right and left and bottom have a wall
db 0b1100 ; 8. positions right and left have a wall
db 0b1100 ; 9. positions right and left have a wall
db 0b0110 ; 10. positions left and left have a walland so on for each row.

Assuming the player is still at the position mentioned above, following pseudo code can test if he is allowed to go right:

PlayerPositionY = 0
PlayerPositionX = 0

AdressLabyrinthDef = ...
WidthOfLabyrinth = 10

goRightAllowed:

 ldx #AdressLabyrinthDef     ; address labyrinth
 lda PlayerPositionY         ; get player y position
 ldb #WidthOfLabyrinth       ; multiply with 
 mul                         ; width of labyrinth
 leax d,x                    ; adjust labyrinth position
 lda  PlayerPositionX        ; load player x position
 inca                        ; since right is +1 
 leax a,x                    ; in x now the correct position that must be tested (from player pos, upper right tile)
 ldb ,x                      ; in b value of that tile
 andb #0b0010                ; is it a tile going down?
 bne moveNotAllowed          ; if so - move not allowed - jump
 leax WidthOfLabyrinth,x     ; check the second involved tile
 ldb ,x                      ; in b value of the tile below the just tested
 andb #0b0001                ; is it a tile going up (upper wall)
 bne moveNotAllowed          ; if so - move not allowed - jump
 ... doSomething if allowed to move
 rts

moveNotAllowed:
 rts

This is roughly the algorythm currently implemented (for one direction).

If a player moves in the labyrinth it now calls a function “is_allowed_direction” – the function returns yes or no – and the game continues.
There is no collision detection involved at all – and the tests that must be done in general are done really fast (compared to collision detection).

The actual implemented routine is a bit more complex than above. To give you a picture just a few more pointers.

– the players “screen” coordinates are completely disjunct from the labyrinth coordinates, but they must naturally be “synced”
– the labyrinth coordinates consist of
* coarse coordinates (which exactly represent the tile positions 6×10 in the case of the above shown labyrinth)
* fine coordinates, which range from -7 to +7. 0 (zero) is the center of a tile, and +-7 is a position close to the edge of a tile.
When a fine positions absolute value reaches eight it resets to the negative and the coarse position is updated accordingly
– the coordinates in the labyrinth start with 0,0 in the top left corner and can only grow “positive” from there, this is because the data representation in memory is just an array – and with these coordinates it can be addressed easily
– some additional testing must be done so the player can not “enter” horizontal lines while going left and right (same for vertical and up/down)
– the routines support player “sizes” so the player can move between the labyrinth walls (in the above picture – the read lines are “wider” than just one pixel)
– using the “fine positioning” – you actually only have to test when the coarse position changes (so -> only every 16 “pixel”) (or – here comes the player width – (16 – playerWidth) )

Thoughts anyone?

Malban