SpritesMind.Net

While I was trying things in my game I have found that if I use 40 like helicopter enemies that each own calculate his own path based on the location of the protagonist the scroll slows a bit.

Well, it isn't optimized but, there is no colision detection yet, so I can get a map of the situation.

So my question is: what kind of AI can I use on my game knowing that some day it will be full of features (music,several scrolls,colisions,...)?
are only precalculated paths suitable? and may be with some pursuing algorithm?
or MD can handle more than that?

or may be I have to expect to not be at 60fps of speed?

Nobody could answer to this question, because this requires strong skills of providence. Tons of variables here: Basic/C/Asm, how much time will take your 'full features', how complex the pursuing algorithm, etc.

Just make tests and see. Generally, I don't think there is a huge difference between precalculated paths and simple pursuing algorithms.

You can check other similar games to see what is surely possible to achieve.

You probably don't need to do long calculations for every enemy every frame. The enemies can take turns doing AI calculations so that on frame 1, calculations are done for enemies 1-10, and on frame 2, calculations are done for enemies 11-20 and so on.

Shiru, my intention is to work with C until realy asm is needed. I only want to know what a action game is capable with several (20-40) independent things moving with an IA, idealy a maximun cota. My intention was to not underrate it, but I think that MD can't perform a A* in this situation, and as long as I saw all comercial games use a precalculate path; but they were created 20 years ago, may be things changed...

Gigasoft, that's a good point! enemies moving in fixed direction and changing their direction at several frames o seconds... I think that that there is a similar IA algorithm.

Thanks!

Sorry for the delay but gmail but the notification mail as a spam...

Well, the Genesis should be able to handle a LOT more than this. You must be doing something pretty complicated to have issues with only 40 helicopters. Can you elaborate?

I don't think it's true that all games use precalculated paths. Some do, for sure, and some use a mixture. But generally a lot of games WILL do exactly what you're trying to do.

You mentioned A* - I'm confused why you would need this to control helicopters?

Finally, you're probably worrying unnecessarily - I can't think of a single Genesis game that has 40 seperate enemies on screen at once. I'm not even sure that'd be very playable...

Hi,
I suggest you to find a copy of AI Game Engine Programming
It's a interesting book because it talks about any kind of games and how AI could be handled.

But anyway, from what I learnt, any game has its own AI engine
This book is just a help to made your own.
or one of these ones (AI for game developer from OReilly also a good one)

just my 2 cents

Thanks KanedaFr! It really sounds interesting.

Snake wrote:I don't think it's true that all games use precalculated paths. Some do, for sure, and some use a mixture. But generally a lot of games WILL do exactly what you're trying to do.

Well, I don't test it in every game. Can you give an example of non-precalculated path? It will be interesting to study.
As far as I remember every action game uses a mix of precalculated path & persuing algorithm.

Snake wrote:You mentioned A* - I'm confused why you would need this to control helicopters?

I think A* is an example for what 16bit action game is not capable to do as is (with no cheats).

Snake wrote:Finally, you're probably worrying unnecessarily - I can't think of a single Genesis game that has 40 seperate enemies on screen at once. I'm not even sure that'd be very playable...

That's true, 40 enemies is too. But, think about 20 enemies (with intelligents shots like misiles) with explosions and other effects that consume cpu. I only want to know where is the limit.

eteream wrote:

Snake wrote:I don't think it's true that all games use precalculated paths. Some do, for sure, and some use a mixture. But generally a lot of games WILL do exactly what you're trying to do.

Well, I don't test it in every game. Can you give an example of non-precalculated path? It will be interesting to study.

It probably isn't the best example given the genre (It isn't a platform game), but a majority of AI controlled opponents act entirely on their own accord in the Shining Force series (Most specifically, the second game, the first one had some ridiculously set AI routines).

eteream wrote: I think A* is an example for what 16bit action game is not capable to do as is (with no cheats).

A* is merely an array of weights for all the positions you could take on a level, then picking a path that minimizes the total accumulated weight between the objects. A full implementation would consider all paths between the objects, and pick the one with the lowest value, but you could do a partial A* pretty easily by only considering paths in the direction of the end point, and/or only considering partial paths (only go X number of units instead of all the way to the objective). In that way, you can make A* work with even 8-bit systems.

8 bit systems often kept the path considered REALLY short, which meant the enemies sometimes got blocked by obstacles. You saw that in games like Tank for the A2600. You could compensate for problems like that by having a table of impassable objects, then when considering the path, look at the table first to adjust which way you consider your partial paths.

Flygon wrote:Well, the Genesis should be able to handle a LOT more than this. You must be doing something pretty complicated to have issues with only 40 helicopters. Can you elaborate?

I agree Geny can do more. Indeed I optimized a bit the code and now it is capable of doing that (using pointers instead "[]" while using an array).

BUT if we consider that:
- 1 instruction for 4 cycles.
- 60 fps
- 40 enemies

we have:
7650000 / ( 4 * 60 * 40 ) =(more or less) 800 instructions per enemy.

Moreover:
- About 30-40% of asm instructions are 4bytes in large (don't look at me, ask gcc).
- You need colision detection, scroll, update sprites,... and VBLANK special precessing things too (palettes,etc...).

So, in this context you are lucky if you have about 500 instructions per enemy. Not so much.

Flygon wrote: It probably isn't the best example given the genre (It isn't a platform game), but a majority of AI controlled opponents act entirely on their own accord in the Shining Force series (Most specifically, the second game, the first one had some ridiculously set AI routines).

As you might know in a turn based game you have up to several seconds to think, while in a action game you have 1/60 seconds at all.

Chilly Willy wrote: [...] but you could do a partial A* pretty easily by only considering paths in the direction of the end point, and/or only considering partial paths (only go X number of units instead of all the way to the objective). In that way, you can make A* work with even 8-bit systems.

Check this:



even this:



You need to calculate at least one time the full path, or put the objects and enemies in strategic positions, that is what all games do, even today, I think.

Chilly Willy wrote: You could compensate for problems like that by having a table of impassable objects, then when considering the path, look at the table first to adjust which way you consider your partial paths.

My idea is to use an extra field in the tile map for collision detection.
You suggest when spawning new random enemies first calculate if they collide with an object, if not, create the new enemy. Is it? Good idea!

UPDATE:

eteream wrote:- About 30-40% of asm instructions are 4bytes in large (don't look at me, ask gcc) *.

This is mainly because I used 8bit access instructions, so in conclusion: avoid (if posible) to use 8bit variables.