Fast (bounding box?) Collision detection

[roondar]

This is really off-topic. Perhaps we should consider discussing this elsewhere

Originally Posted by Shatterhand

I've said this here once before, so I'll be repeating myself.

But no. Super Mario Bros 3, Megaman 2, Ninja Gaiden, Shadow of the Ninja... the game that inspired my nickname (Shatterhand)...

You're missing my point - it's not about comparing games genre by genre. It's about games as a whole. I've had far more hours of entertainment and immersion from some Amiga games than I did from all NES games I ever played (including the ones I've played in recent years).

Granted, these Amiga games tended not to be action games, but that is besides the point here. This is not to say that action games are no fun. I can still remember playing Speedball II for hours. Great game, easily top tier NES (or even SNES) material. Oh and Dynablaster, which is literally a console game on the Amiga and a damn good one at that.

On a personal note: what I always find striking in these discussions is how it just doesn't fit with my personal experience. Despite the so called quality difference in favour of consoles, all the 'console' kids I knew ended up playing C64/Amiga games for hours at my house, generally preferring it to playing the console games.

And then you have the shoot'em ups... Zanac, Gunnac, Recca, Crisis Force, Gradius 2... again, nothing on Amiga can touch those gems in terms of pure gameplay quality.

And yet, in another thread (IIRC) you recently pointed to Apidya as a game that could (paraphrasing your words as I understood them) pretty much be a top tier console shooter. Which is something I've seen argued before a number of times on the net. I happen to agree with that sentiment and as such disagree with what you say here.

I didn't have a NES back at the time, but owning one now and finally getting the gripes with its library, I really can understand why it was so damn popular. It really has a huge library of amazingly good games.

Like most retro consoles, the games on the NES are generally (IMHO) overrated. That's not to say library is poor. It has some great games and some genuine classics in it. But that doesn't mean that all of the games are good or even that the games are generally good.

Many NES platformers (including quite a few of the classics), for instance, commit the horrible, horrible design sin of making the player jump back on a hit. That is (IMHO) one of the worst things in gaming ever and the NES pretty much made it popular. Not a good thing.

And yes, I'm dead serious on that point. It's totally arbitrary and generally leads to many unfair deaths. It can totally spoil a game play session or even game. It's one of the main reasons I thoroughly dislike Turrican III. I'd rank it as just as bad as leaps of faith or 'please redo the game again to get the ending', which is also really bad design.

This doesn't mean the Amiga doesn't have great 2D action games. It does. But.... it's just too hard to compete with what the japanese devs were doing back at that time.

Personal preference plays a massive role in this. I personally consider some of the Amiga non-action games to be better than just about all action games I've seen on consoles (by virtue of how they drew me in and made me 'forget' about the outside world for days).

It's like has been said on another thread. I always felt european devs were too busy trying to push the hardware to its limits instead of designing games that were *really* good.

There are killer games originating in Europe. Some of the best regarded games ever come from Europe. Best not to generalise

If I didn't agree with you I wouldn't be trying to make an Amiga shoot'em up right now

Looking forward to it. And being on the Amiga, you can always put more bullets, objects and scenery in than the NES could ever handle

[Shatterhand]

Looking forward to it. And being on the Amiga, you can always put more bullets, objects and scenery in than the NES could ever handle

Only if I was a good coder, which this thread already proved I am not

Yeah, I am feeling guilty for derailing a topic for the 2nd time in less than 24 hours. Back to fast collision detection, hehe

[zero]

Originally Posted by Shatterhand

The NES is full of brilliant 2D platform games that *no* Amiga game can even dream of touch. Everytime I'm playing with my NES I can't help think "Holy shit, this could be easily ported to Amiga and if it was done back at the time it would be a KILLER game on it".

European and US developers had a very different style. They just didn't do that Japanese style of platform and shumup game. Occasionally they came close, Apidya for example, but usually they ended up Gianna Sisters - a bad knock off that didn't understand what made Mario great (his movement) and was hobbled by being controlled with a one button joystick.

Western developers did make good games, but they tended to be slower paced, more focused on puzzles, and worst of all designed to run on a wide range of 8 and 16 bit systems.

Many Amiga games were hobbled by being co-developed for the Atari ST, for example.

It's like has been said on another thread. I always felt european devs were too busy trying to push the hardware to its limits instead of designing games that were *really* good.

That's an interesting point that I hadn't considered. There certainly were a few games that looked pretty by played badly, Shadow of the Beast being a great example.

[zero]

Originally Posted by roondar

You're missing my point - it's not about comparing games genre by genre. It's about games as a whole. I've had far more hours of entertainment and immersion from some Amiga games than I did from all NES games I ever played (including the ones I've played in recent years).

All the classic NES games are Japanese and a very different style to the mostly western games on the Amiga. You can't really compare them directly, it's like trying to decide if heavy metal or jazz is better. Both have their unique charms.

Gamesack did a review of the CD32 once. They didn't like most of the games, and in some cases the criticism was fair because the CD32 wasn't all that competitive. Often it was just that the games were not console style and what they were used to though.

Both are an acquired taste it seems.

[Shatterhand]

AAAANNDD....... we're are moving to split another topic about console games...

That's an interesting point that I hadn't considered. There certainly were a few games that looked pretty by played badly, Shadow of the Beast being a great example.

Not a few. A lot I always felt european games were made by programmers who didn't even played games at all. Sometimes they got it right, and I still wonder if it wasn't by pure dumb luck. To this day I still think Bitmap Brothers didn't know what made Speedball 2 or The Chaos Engine good games, they got them right by luck.

In the other hand japanese devs weren't trying to FIGHT the hardware, instead they tried to do good games that would work easily on the hardware. Look at Super Mario Bros... scrolls only one direction, isn't pushing the NES at all, friggin brilliant game.

Another thing that I feel it was a big difference was the size of the staff. Yeah, japanese games also had those "Whole game coded by a single programmer who had just graduated from university working on a small office shared by other 5 coders", but the bigger releases had proper staff. Looking at Vampire Killer on MSX (Its Castlevania version), the credits roll at the ending show SIXTEEN people working on the game. What amiga game had 16 people working on it? And that was an 8 bits game!


I agree there's a very obvious difference between American, European and Japanese devs, at least during the 80s and 90s. At that time you would never see a japanese dev doing a game like Cannon Fodder or Syndicate, both amazingly good games. But at that time what we were playing the most was pure arcade games, and on this area the Japanese guys were gods.... and I think that's the main reason: They were more focused in bringing a good game than pushing the hardware.

I don't think it's a coincidence the games I find that push the Mega-Drive hardware to its limits are NOT Japanese, but western ones (Batman & Robin, Vectorman, Zero Tolerance, Red Zone...)

Are they better games than the most impressive-coded japanese games on the system? (Alien Soldier, Contra:Hard Corps, Gunstar Heroes...) Absolutely not.

[Photon]

Originally Posted by zero

I guess you haven't played the original arcade version much. I own an original board, BTW.

My collection was 4 original cabinets and a Jamma cabinet that took my 20 boards, including many of the classics you can think of. I've repaired arcade PCBs and supplied monitors to a local distributors. I was never able to repair my Asteroids PCB, and I never owned a Pac-Man board, only a Ms. Pac-Man board.

I think most of us here have the experience of games from the 80s to today, especially 2D games such as arcade and the arcade ports we got on Amiga.

I mention flickering because on arcade/port, this wouldn't be tolerated. I'm here to say that Bullet Hell is irrelevant for Amiga, and that competent collision detection is both possible and necessary to produce Amiga games that are better than the ones we got.

[Hewitson]

Originally Posted by roondar

There's actually Amiga games without flickering that are as good as some of the best NES games

Yeah, I couldn't disagree more with this, unfortunately.

Name one Amiga game as good as Metroid? Or Contra? Or Final Fantasy? Or the Mega Man series? They simply don't exist.

[roondar]

Originally Posted by Shatterhand

I always felt european games were made by programmers who didn't even played games at all. Sometimes they got it right, and I still wonder if it wasn't by pure dumb luck. To this day I still think Bitmap Brothers didn't know what made Speedball 2 or The Chaos Engine good games, they got them right by luck.

The above statement is silly. There was and is tons of genuine skill in Europe. Some of the best games ever made came from Europe.

The notion that European games that were good were only an 'accident' is really rather insulting to the people involved, don't you think?

But at that time what we were playing the most was pure arcade games.

I certainly wasn't. All it took for me to realise there were much better things than action games were Elite and Lords of Midnight on the C64. Ever since then, I've played whole bunches of the more cerebral games out there and loved it. Not to say I don't like action games (far from it, love me a good SHMUP. Even got a PCE for more shooters. Also like me a good side scroller), but overall I've liked the less action-y games way better.

Which might be why I keep being mystified with at all this 'consoles rock' stuff

Originally Posted by Hewitson

Yeah, I couldn't disagree more with this, unfortunately.

Name one Amiga game as good as Metroid? Or Contra? Or Final Fantasy? Or the Mega Man series? They simply don't exist.

Nonsense. The above list is purely based on your personal preference.

For instance: I personally find the Mega Man series and Contra to be some of the most overrated games in history. I also think that the first Final Fantasy worth playing is FF-III/VI and the ones before that were average at best. Of the games you listed, the only one I personally feel is any good is Metroid. And I still think even that is overrated. I don't think it's bad, but I don't think it's amazing either.

Over and over we get people claiming the Amiga is bad for games because they like some console action game or another more than what was on the Amiga. Well, I had more fun with Elite:Frontier 2 than all of those games you listed combined. I'd exchange all of them for the poorly converted OCS Amiga version of Civilization in a heartbeat. And that's not even getting into the wonders of those lovely SSI titles, which all stand head and shoulders above console action games in my mind.

As for that one game. I'm sure it has to be an action game that could also be on a console for you to even consider recognizing it, so I'll offer you Dynablaster. This is Bomberman and it plays exactly the same as on consoles. Bomberman is widely recognized as a true classic console game and generally considered one of the best games ever made. It is available on the Amiga. Even runs in 60Hz.

Now, if I understand the rules of the 'Amiga vs Consoles' game well enough, you're now going to claim that Dynablaster/Bomberman is actually not a good game because... Reasons. Or, you'll move the goal posts and admit it is good but then go and claim it's the only example and therfore it doesn't count.

[phx]

(mainly played Arcade games)

Originally Posted by roondar

I certainly wasn't. All it took for me to realise there were much better things than action games were Elite and Lords of Midnight on the C64. Ever since then, I've played whole bunches of the more cerebral games out there and loved it. Not to say I don't like action games (far from it, love me a good SHMUP or side scroller), but overall I've liked the less action-y games way better.

Which might be why I keep being mystified with at all this 'consoles rock' stuff

Same here! I can only agree.

I guess the European games market was different to the American and Japanese, where consoles dominated. European gamers saw the numerous advantages in having a full computer. And many of them became creative with it. I loved the variety on the Amiga and most Arcade games quickly became boring to me, while I could play "Player Manager" or "Civilization" for months. Never felt the need for a games console in my whole life...

[Shatterhand]

The notion that European games that were good were only an 'accident' is really rather insulting to the people involved, don't you think?

I find every game Bitmap Brothers did before Speeball 2 were garbage. Looked good, played like shit. Gods included.

Then comes Speedball 2. GREAT, fun game to play with lots of nuances on gameplay. Then comes The Chaos Engine, another very well designed game which is great to play.

Then comes The Chaos Engine 2: Huge piece of crap. And later they try to remake Speedball 2 at least twice. Both times it's, again, awful.

When I say "Got the game right by dumb luck" I am always thinking about Bitmap Brothers. But when I look at the dev team at Team 17, it's hard to not think the same thing.

In the other hand... yeah, its unfair from me to put everyone on the same bag. I believe Factor 5 did know and care how to do good games, as obviously Sensible Software too (Even though I am really hugely dissapointed with Jon Hare and the Sociable Soccer debacle).

But I loved that someone mentioned Metroid. I don't think there's anything like it on Amiga. I only got to play Metroid games recently (I never had any nintendo systems back at the day), and they are incredibly good for their time. Super Metroid was really lots of fun to play (even if I had some issues with its control scheme)... it's something the Amiga could handle very easily...

I find it curious because there are actually lots of european games that are, like, open and about exploration and finding out things, yet I can't name one that's as well designed and polished as Super Metroid.

[roondar]

Originally Posted by Shatterhand

I find every game Bitmap Brothers did before Speeball 2 were garbage. Looked good, played like shit. Gods included.

To each their own, I actually liked Speedball I as well and found Gods a decent, if not spectacular game.

In the other hand... yeah, its unfair from me to put everyone on the same bag. I believe Factor 5 did know and care how to do good games, as obviously Sensible Software too (Even though I am really hugely dissapointed with Jon Hare and the Sociable Soccer debacle).

I'd say DMA design was also pretty good, as were quite a few others really. But I'm not in the mood for lists, I already spent too long on the forum today.

But I loved that someone mentioned Metroid. I don't think there's anything like it on Amiga. I only got to play Metroid games recently (I never had any nintendo systems back at the day), and they are incredibly good for their time. Super Metroid was really lots of fun to play (even if I had some issues with its control scheme)... it's something the Amiga could handle very easily...

Well, there is Power Glove Reloaded. But that might not completely qualify as it's a bit short on items to collect. Nice game though, looks great too.

It is indeed curious no one else has tried for a 'Metroidvania' yet on the Amiga (past or present). Should fit the hardware quite well, actually - you could even do nifty things like having levels that don't use standard 16x16 tiles as the individual rooms/areas in Metroid tend to be quite small so it can probably all fit without the need for wrapping displays. The C64 did get a few over the last few years, but as yet, nothing on the Amiga.

[Shatterhand]

It's a huge work to do something like Metroid for Amiga as a spare-time-hobby job. I've been thinking about something like that with flicker-screens on Amiga... but the work would be huge really.... and I still have lots of other stuff I would like to do on the machine

Nah, I agree with you. I was unfair. DMA Design made great games too. Those guys whoe made The Killing Game Show and Geometry Wars also did some great games (Forgot their name), and yeah, we could keep listing a few more. Yes, my statement before was kinda unfair indeed.

[zero]

Originally Posted by Shatterhand

Looked good, played like shit. Gods included.

Gods is one of the best games ever made!

I think it really depends what type of game you prefer. There is certainly no equivalent to Mario on the Amiga, but also there is nothing like Gods on the NES.

[Retro1234]

Bitmap Brothers games are shit I like brainless button bashing

[Photon]

Originally Posted by roondar

This is really off-topic. Perhaps we should consider discussing this elsewhere

Agree, let's not compare 'which game is more fun' and definitely not platforms in this forum.

But Amiga games are ofc still highly relevant if they follow the topic: Fast Collision Detection. And so are techniques from any platform that can be implemented on Amiga (while being fast, ofc).

[roondar]

Well, I've not actually done any tests here but the one remaining 'out there' idea I have would be to process objects in groups that act as one bigger object - until the grouped entity hits anything and only then look into what entity in the group collided. (effectively this is bounding box collisions where some objects are grouped into a single, bigger box and only 'separated' when a collision with the big box is detected)

This would work best if the object tested is not a grouped one but rather a separate one and the objects tested against are grouped. In theory, this should allow the number of tests to go down because you're only testing against bigger groups. However, adding objects to the group naturally also takes time to do. And naturally, this is only useful if objects can be reliably grouped together over multiple frames. A game that has all of it's objects moving freely will probably not work for this.

As such, I'd say such an approach might work best if you can 'pre-bake' the collision groups and use some sort of group-anchor as the point where the big box is 'drawn'.

I'm not certain it'd actually save time though, it probably rather depends on object spread on screen.

Other than that, your initial points are still the best overall idea: reduce the number of objects that need to be tested by using knowledge about the objects to exclude them from tests.

[pink^abyss]

Another option is to use morton codes. This works very fast, and can be easily combined with position fuzzing to test also objects outside the current morton slot.
I used that approach in my game "Tiny Galaga". There i had to test 8 player bullets with 32 enemies and the player with 32 enemies and 8 enemy bullets (so over 300 comparisons in worst case). Axis sorting was not possible because enemies could be clustered on X and Y axis.

[Raislin77it]

Originally Posted by pink^abyss

Another option is to use morton codes. This works very fast, and can be easily combined with position fuzzing to test also objects outside the current morton slot.
I used that approach in my game "Tiny Galaga". There i had to test 8 player bullets with 32 enemies and the player with 32 enemies and 8 enemy bullets (so over 300 comparisons in worst case). Axis sorting was not possible because enemies could be clustered on X and Y axis.

very interesting tip the Morton Code ,thanks

[buzzybee]

Never heard about the "morton code" before, so had to google it. Pretty interesting concept. Not sure in how far it can be faster than simply comparing coords: If I understood it right you attach an quadrant attribute to each moving object, and simply compare if two objects move within the same quadrant, and just in case of a hit init more sophisticated methods of collision detection. But you still have to update this attribute each frame for each object, no?

[pink^abyss]

Originally Posted by buzzybee

Never heard about the "morton code" before, so had to google it. Pretty interesting concept. Not sure in how far it can be faster than simply comparing coords: If I understood it right you attach an quadrant attribute to each moving object, and simply compare if two objects move within the same quadrant, and just in case of a hit init more sophisticated methods of collision detection. But you still have to update this attribute each frame for each object, no?

You could call it a 1-dimensional spatial hashing method. Anything that moves would need to update it's morton codes in the data structure. You can store the pointers to the objects sorted in a linked list or in fixed sized bins. For simplicity i used fixed sized bins with a counter. For 32 enemies it took about 8% CPU time (in my 'Tiny Galaga'). For potential collision testing it's then only a lookup into the correct bin. Testing was then much faster then building the bins.

In general this method does only pay off if you need a large amount of tests. If you have only a few dotzend tests or widly different AABB sizes then brute force will win.