Overhead driving engine development

[presh]

The biggest downside to playing your game over and over again is that you get so good at it, that you overlook how a first-time player will react to it.

Indeed, I remember having a good discussion about this a while back

I had to add two difficulty levels to Yankee (medium and easy), because virtually everyone had complained the game was too hard and no one lasted more than a few seconds. Me? I thought it was still way too easy even on hard.

Heh... yup, I toned down the difficulty of the 1st level of Hell Yeah! by making the standard enemies all one-hit-wonders. And in contrast to your own situation, I found myself adding the Medium and Hard difficulty levels because I found the initial (now known as Easy) setting an absolute walk in the park... still packs a challenge on Hard for me, mind!

[presh]

I'm going to need some collision detection between 45-degree diagonal lines and AABBs, as diagonal lines would be quite difficult / costly to mimic using just the AABB routines I have so far, and I figured there must be a quicker way. After a bit of sketching on graph paper, I figured out a simple algorithm to do it.

To make sure I'd done it right, and to avoid the agony of countless pen-and-paper run throughs, good old BASIC came to the rescue!

https://www.youtube.com/watch?v=uyK7FwlMUs4

Having come up with a little algorithm to detect a collision between a diagonal line segment and an axis-aligned bounding box (AABB), I wanted a visual playground to test it, so I wrote a short BASIC program to do so.

The AABB is represented by the black box and the diagonal line segment by the stars. The line can be moved using the keyboard. The coordinates and size of each can be adjusted at the start of the program listing (not seen here). If a collision is detected, the border turns red.

The next step is to convert the check (seen at the start of the video) to machine code, keeping the rest of the BASIC program to set up the values, move the line around and display the results. Once verified correct, the Z80 routine can be integrated into the overhead driving engine.

For those interested, the variables are:
rx , ry : line segment coordinates (position of top-left cell)
rl : length of line (0 → 1 cell; so in this video, rl = 5)
aminx, amaxx, aminy, amaxy : coordinates at the minimum & maximum points of the AABB on each axis (i.e. its four corners)
Note that coordinates follow the Spectrum's PRINT AT coordinates, i.e. increasing y moves DOWN.

I also have the algorithm for a diagonal line in the other direction (rising from left to right) completed in BASIC which is very similar, with just a few tweaks to reverse the x-axis conditions.

[patters]

I write test programs like this. Glad to see other people do it too

[presh]

OK, so some of you will have already noticed that this became my entry for this year's ZX Dev Media Demakes competition, Rival Gangs

It's available to download here: https://zxpresh.itch.io/rival-gangs

Unfortunately the tight schedule of the competition meant I didn't have time to keep updating this thread, so apologies to those who were interested in watching it grow gradually!

However it was a really useful experience having AN ACTUAL DEADLINE to finish the game by, forcing me to make decisions about which bits were "necessary" and which were "nice to have", etc. I know a few of the other devs have faced the same dilemma! If I'm 100% honest, I'm a bit gutted about some of the things I didn't have time (and more recently, space) to include... so while this is a 100% complete game in itself, it definitely isn't the last you'll see of this engine!

[arjun]

Yeah, a little overlap was inevitable as I'm only using 2 axis-aligned bounding boxes (AABBs) for the cars as computationally they're very cheap / fast. I was worried that the result might turn out crap, but it actually feels pretty good especially now it can make the distinction between "head on" collisions and ones with some direction in common, setting values accordingly.

Here's an example of how the AABBs (black/green) are arranged for one of the directions:


And @Turtle_Quality is right that the cars don't know how to reverse at the moment. They just put their foot down and try to steam ahead no matter what's happening! I need to add a few more behaviours to the cars to make them less aggressive & help them find their way out of sticky spots...

I seem to have missed this thread entirely... But very cool looking game!

I'd like to know more about how you get away with just using 2 AABBs for collisions. Since the car is squished along one axis more than the other (i.e rectangular) don't you need 3 AABBs at minimum? One for vertical, one for horizontal and one for diagonal?

[presh]

I'd like to know more about how you get away with just using 2 AABBs for collisions. Since the car is squished along one axis more than the other (i.e rectangular) don't you need 3 AABBs at minimum? One for vertical, one for horizontal and one for diagonal?

The first reason for choosing 2 AABBs was that my initial tests with 1 just felt rubbish. Far too much overlap between the colliding sprites! I had anticipated this, however we have to start somewhere

Tests with 2 were much more satisfying, and there was much less "catching" of protruding corners on each other than I had anticipated. There's still a little visible overlap between the colliding sprites of course, but this does help make the cars seem more malleable rather than being rock-solid.

Speed was the most crucial factor, however. When two cars collide with 2 AABBs per car, you have to consider collisions between:

Code: Select all

a_outer --- b_outer
if collision:
  a_front --- b_front
  a_front --- b_rear
  a_rear --- b_front
  a_rear --- b_rear

Upping this to 3 AABBs, this becomes:

Code: Select all

a_outer --- b_outer
if collision:
  a_front --- b_front
  a_front --- b_middle 
  a_front --- b_rear
  a_middle --- b_front
  a_middle --- b_middle
  a_middle --- b_rear
  a_rear --- b_front
  a_rear --- b_middle
  a_rear --- b_rear

So the code size and computation time for resolving collisions both rise exponentially (power 2) as we add more AABBs.

It would also mean that the AABBs would have to be variable size - at present, they are all 8x8 pixels for cars - which would require more memory reads when updating the AABBs. At present, I only need to look up 4 values per AABB (top-left offset of each AABB from the car's origin). I would need a further 4 lookups (width & height of each AABB) to implement variable AABB dimensions on a 2 AABB car. For 3 AABBs, this rises to a total of 12 lookups vs the current 4.

Note, even 2 AABBs is somewhat wasteful, as when the car is facing N/E/S/W the car can be modelled accurately with 1... but the logic to figure this out on a case-by-case basis is likely to nearly as long as just getting on with it and processing both, and would chew up more memory with the extra code too.

So yeah, 3 AABBs would be nice - but was deemed not feasible for such a small boost in accuracy.

Hope that answer your question

[arjun]

I'd like to know more about how you get away with just using 2 AABBs for collisions. Since the car is squished along one axis more than the other (i.e rectangular) don't you need 3 AABBs at minimum? One for vertical, one for horizontal and one for diagonal?

The first reason for choosing 2 AABBs was that my initial tests with 1 just felt rubbish. Far too much overlap between the colliding sprites! I had anticipated this, however we have to start somewhere

Tests with 2 were much more satisfying, and there was much less "catching" of protruding corners on each other than I had anticipated. There's still a little visible overlap between the colliding sprites of course, but this does help make the cars seem more malleable rather than being rock-solid.

Speed was the most crucial factor, however. When two cars collide with 2 AABBs per car, you have to consider collisions between:

Code: Select all

a_outer --- b_outer
if collision:
  a_front --- b_front
  a_front --- b_rear
  a_rear --- b_front
  a_rear --- b_rear

Upping this to 3 AABBs, this becomes:

Code: Select all

a_outer --- b_outer
if collision:
  a_front --- b_front
  a_front --- b_middle 
  a_front --- b_rear
  a_middle --- b_front
  a_middle --- b_middle
  a_middle --- b_rear
  a_rear --- b_front
  a_rear --- b_middle
  a_rear --- b_rear

So the code size and computation time for resolving collisions both rise exponentially (power 2) as we add more AABBs.

It would also mean that the AABBs would have to be variable size - at present, they are all 8x8 pixels for cars - which would require more memory reads when updating the AABBs. At present, I only need to look up 4 values per AABB (top-left offset of each AABB from the car's origin). I would need a further 4 lookups (width & height of each AABB) to implement variable AABB dimensions on a 2 AABB car. For 3 AABBs, this rises to a total of 12 lookups vs the current 4.

Note, even 2 AABBs is somewhat wasteful, as when the car is facing N/E/S/W the car can be modelled accurately with 1... but the logic to figure this out on a case-by-case basis is likely to nearly as long as just getting on with it and processing both, and would chew up more memory with the extra code too.

So yeah, 3 AABBs would be nice - but was deemed not feasible for such a small boost in accuracy.

Thanks for the detailed explanation!

However, what I meant was, switch out the 'current' AABB depending on the direction of the car, so even though you have 3 different AABBs, you test with a single one on collision (or 2 max if you wish to retain the inner one) depending on which one is switched in.

Let's say you have A, B and C defined as AABBs for horizontal, vertical and diagonal directions (assuming variable width and height). If car is travelling horizontally you make A as current and test all collisions with it. If vertical, then test against B etc.

Or maybe I'm underestimating the complexity of the actual implementation.

[presh]

Thanks for the detailed explanation!

However, what I meant was, switch out the 'current' AABB depending on the direction of the car, so even though you have 3 different AABBs, you test with a single one on collision (or 2 max if you wish to retain the inner one) depending on which one is switched in.

Let's say you have A, B and C defined as AABBs for horizontal, vertical and diagonal directions (assuming variable width and height). If car is travelling horizontally you make A as current and test all collisions with it. If vertical, then test against B etc.

Or maybe I'm underestimating the complexity of the actual implementation.

Ah, ok... sounds like you you interpreted what I was saying as "I'm only using 2 AABBs of predetermined position and size to cover all collision possibilities", whereas what I meant (and am actually using) is 2 AABBs per angle, i.e. the 2 AABBs also change position to give the best-fit with the car graphics for a given angle, and there are 16 possible angles, so in total I have 32 offset AABB definitions.

But I'm also a bit confused as you seem to be suggesting using a single AABB (box C) to detect collisions when facing diagonally? So apologie if I'm not following you still. Happy to clarify anything though

[arjun]

Ah, ok... sounds like you you interpreted what I was saying as "I'm only using 2 AABBs of predetermined position and size to cover all collision possibilities", whereas what I meant (and am actually using) is 2 AABBs per angle, i.e. the 2 AABBs also change position to give the best-fit with the car graphics for a given angle, and there are 16 possible angles, so in total I have 32 offset AABB definitions.

Ahh... so you're rotating the AABBs with the car in multiple angles. Sorry, I misread your original post then because I thought you were using only 3 degrees of rotation (horizontal, vertical and diagonal). lol. My bad! Ignore what I said then as I was indeed suggesting using a single AABB (albeit switching as required) for the three cases.

[presh]

Little update:

Saved about 1K of memory via a few optimisations. One was to switch as many JPs as reasonably possible to JR, which I thought might adversely affect the speed. Thankfully it doesn't seem to have had a noticeable effect. I was kinda hoping that, as JR [condition], n is faster than JP if the condition isn't met, that I might even make enough savings from that to cover the extra overhead incurred! But to be honest, I wasn't really checking the code closely - I just wanted to see what the maximum space savings could be. I might attempt to refactor the code later to make fastest use of JP & JR's relative strengths if I have enough space left*

Started building the missions! And now I have some memory (albeit not much!) to add extra features to make these a bit more exciting than just "drive here, ok now drive here". I figure a lot of the logic I need for these is already written - for example, spawning a pedestrian at a certain position - so hopefully mostly a case of stripping some of the currently-baked-in-as-it's-only-used-once logic out into CALLable routines. Nevertheless, I expect that trying to spawn cars for missions will be an absolute pain in the arse.

Added a little flashing arrow to show where you're supposed to go. It sucked having to cut this from the competition release, as the final mission (and only "proper" mission in that version) is probably a right bast without any idea where to go!


*

[presh]

I took a bit of time away from coding missions to attempt adding some AY music, in the hope of giving vehicles a different soundtrack in the style of GTA. Alas, this required a complete rewrite of the screen blitter to no longer use the stack, and combined with the extra CPU time required to play the music the game became noticeably slower

Even if this hadn't been enough to bail on the idea already, finding enough memory to store the music was also a problem... most of the extra space afforded by the 128K pages has already been filled with car and map graphics, map data, etc. so additionally I would have to compress the music data (and hope they all fit once done!), then decompress when a player enters a car, which would create a pause when that happens... though how long I can't be sure, as I never attempted to try!

So yeah, I think it's time to return to the missions & get those finished. I aim to get the whole thing finished & ready for release by late February / early March...

[Ivanzx]

Maybe including a nice AY tune in the menu would already help Something that sounds kind of like GTA?

[Nitrowing]

A different tune for different missions?

[presh]

A different tune for different missions?

Though this probably does somewhat negate the issue regarding song decompression time , it's sadly not doable, due to how slow the game runs when playing music.

Maybe including a nice AY tune in the menu would already help Something that sounds kind of like GTA?

Yeah, I think this is about the best I can aim for!

[presh]

Working on one of the later missions for Rival Gangs EXT... bit of a bloodbath!