Game Dev - Handling Enemy Waves and Pathing

[3qX21hU5]

So currently me and scriptcoder are working on a little project for fun and it is a simple 2D vertical space shooter.

Anyways I was wondering how you guys would go about handling different enemy waves and each wave's path finding. We decided since we both know Python we would be developing it as pure python (Since I would like to get more familiar with Python development) and if we need more performance later we can port some code to C++.


Right now I am thinking something a long the line as a time line for each level. Throughout that time line there will be certain points where certain enemies will spawn. So when that level hits that certain point it will tell the game to add a certain enemy to the active game objects list to be drawn.

For example lets say a level lasts for 2 minutes or something. Throughout that 2 minutes there will be certain points in time that trigger a spawning of enemies. Each of them points could spawn a certain enemy or even just a random enemy taking from a list.

For the path finding I was probably thinking about just starting out with hard coding each enemies path inside of its class so it knows where it needs to go and what it needs to do.

Though I also though maybe having a file that describes all the different paths a enemy could follow and then each enemy can randomly select a path to follow out of a subset of that list. Which would give a bit more randomness to the movements I think.

Anyways how do you guys go about this? Or any flaws you see in what I was thinking?

[N36fSL3A]

Will there be obstacles?

[3qX21hU5]

What does that matter but no there won't really be obstacles other then other enemy ships it's a standard space shooter... And really no offense meant by this but not really looking for help from you fredbill again no offense.

[chrisname]

No offence meant by this, Zereo, but you're the worst kind of person. Again, no offence.

See how that doesn't work?

[ModShop]

You could use "spawners" that are activated at certain timestamps to handle waves. For example, at X seconds spawner A creates Y number of Z enemies at/around it's position. Then you just place spawners wherever you see fit and set them to go off together to create waves. You could also have spawners that are activated if the number of enemies falls below a certain threshold. If you keep everything generic it would be very easy to alter gameplay for varying difficulties or even different modes.

As for path finding, it would probably be enough just to hardcode (or load from configuration files) the paths various types of enemies would follow. There's really not much of an AI aspect in the paths themselves, it's more in the spawning.

[N36fSL3A]

:( Well I was going to give you info about how I was planning on spawning stuff in the space shooter I was working on (Kinda on/off now). I was going to say the same as ModShop, but a little different. D;

[Disch]

I would probably approach wave generation with something like a combination of time delay + a "catch up" so that the player doesn't get overwhelmed if they fall behind. So maybe the level designs would look something like this:

<wave info>
<time delay>
<wave info>
<time delay>
<wave info>
<pause>
<wave info>
etc


where 'pause' would wait until all on-screen enemies are killed (or until fewer than 'X' remain... or until a specific enemy is killed)


The waves themselves would indicate which enemy to spawn (obviously), a quantity, as well as a delay between enemy spawns. So you can have some waves where the enemies are grouped closer together than others.

Also -- be sure to keep this delay independent of the delay between waves so that you can spawn multiple waves at once... and or start spawning a new wave while the previous wave is still spawning.



As for enemy patterns... if you're going to be doing this in Python I would just hardcode the logic. Maybe derive a class for each enemy and give them all their own logic function.

Typically the AI in vertical shooters isn't very complicated... so I wouldn't expect it to get out of hand. They usually just fly back and forth shooting bullets. The trickiest thing you'll have to do is probably have them dive at the player, and even that isn't difficult.

Though I also though maybe having a file that describes all the different paths a enemy could follow and then each enemy can randomly select a path to follow out of a subset of that list. Which would give a bit more randomness to the movements I think.

That's an interesting idea. Though it's atypical of vertical shooters I've played. It might make the enemies seem "disorganized" in that you have a wave of 10 enemies but they're all doing different stuff. But then again maybe that's not a bad thing? It's worth a try.

And really no offense meant by this but not really looking for help from you fredbill

lol. Harsh.

[3qX21hU5]

ModShop wrote:

You could use "spawners" that are activated at certain timestamps to handle waves. For example, at X seconds spawner A creates Y number of Z enemies at/around it's position. Then you just place spawners wherever you see fit and set them to go off together to create waves. You could also have spawners that are activated if the number of enemies falls below a certain threshold. If you keep everything generic it would be very easy to alter gameplay for varying difficulties or even different modes.

I like that idea thank you ModShop. It makes the game more dynamic then just the standard spawn X enemies at time Y. And as you said makes it easier to alter the game play difficulty and other aspects. Thanks again man.

ModShop wrote:

As for path finding, it would probably be enough just to hardcode (or load from configuration files) the paths various types of enemies would follow. There's really not much of an AI aspect in the paths themselves, it's more in the spawning.

Ok wasn't really sure if hardcoding would be enough. Though I think I might just place the pathing in a config file so other enemies can use it also.

[Paoletti301]

Will there be obstacles?

-fred

What does that matter

-zereo

he was asking will there be obstacles because his answer would probably be based on your response. no one likes watching enemies fly through walls etc.

anyways, being as this is a vertical space shooter, i would say stick with patterns, if its going to be a bullet hell that is. randomness in a bullet hell game would be pretty annoying and unfair to the player. thats what i would do at least, make it like an enemy ballet

[N36fSL3A]

I thought the space ship was like so. http://toucharcade.com/2010/07/08/ultraviolet-dawn-new-open-space-shooter-trading-game-free-for-1st-day/

I thought you stay stationary and move around 360 degrees.

[3qX21hU5]

Disch wrote:

I would probably approach wave generation with something like a combination of time delay + a "catch up" so that the player doesn't get overwhelmed if they fall behind. So maybe the level designs would look something like this:

<wave info>
<time delay>
<wave info>
<time delay>
<wave info>
<pause>
<wave info>
etc


where 'pause' would wait until all on-screen enemies are killed (or until fewer than 'X' remain... or until a specific enemy is killed)

Ya that was the tricky part. Finding a way so that the player doesn't get overwhelmed with enemies on the screen yet still having some sort of timeline for the level. I like the idea of waiting to spawn more until certain criteria are met (Certain amount of enemies are left, or a certain enemy is dead, ect). Maybe combine that with the spawners idea where each spawner has a certain "checkpoint" they have to reach before spawning another wave.

That's an interesting idea. Though it's atypical of vertical shooters I've played. It might make the enemies seem "disorganized" in that you have a wave of 10 enemies but they're all doing different stuff. But then again maybe that's not a bad thing? It's worth a try

.

Yea you might be right it might make things way to disorganized. Maybe tweak it a bit so the whole wave of enemies can randomly select from a subset of pathing directions. That way each enemy in the wave isn't flying off in a bunch of different directions and they are still uniform but the player still doesn't know exactly which path that wave will be taking?

anyways, being as this is a vertical space shooter, i would say stick with patterns, if its going to be a bullet hell that is. randomness in a bullet hell game would be pretty annoying and unfair to the player. thats what i would do at least, make it like an enemy ballet

I was thinking more of a mix between a bullet hell type game and a standard space shooter. Just trying to find a good medium at the moment.

Thanks for all the ideas guys.

[D80DSL3A]

I'm with Disch regarding the spawning. I've used a method based on timing with a restriction on the number of baddies presently in play to control spawning rates flexibly enough.

I have what I think is a good method for the pathing of enemies.
A path can have an arbitrarily complex shape when assembled in sections (or legs). I create a class hierarchy of legs with different shapes, one class for a straight line, another for circular arcs, parabolic arcs, etc. The leg::move() is therefore virtual. A path is assembled in a linked list fashion, with each leg having a pointer to the next leg of the path (and perhaps the previous leg in doubly link list fashion if you desire motion in either direction along the path).

Each leg class has at least 2 constructors. One ctor is for the 1st leg on the path and takes arguments specifying all parameters for the leg. For the straight line leg it would take both end points as arguments (and assign pLegNext = NULL). For a circular arc leg this ctor takes the start point, center point and the angle through which the leg sweeps.
The 2nd ctor takes a pointer to the previous leg on the path as an argument so the legs can be joined (use the endpoint of the previous leg as the start point of the leg being constructed), and so the linkage can be assigned ( prevLeg->pLegNext = this; ). This ctor also takes the leg endpoint as an argument.

I create a config file with arguments for all legs on all paths to be constructed for the game. From this file I create a vector<leg*>. In a config file for the enemies I provide an unsigned int as index to the 1st leg for its path in the vector<leg*>. Finally, the leg::move() returns a leg* to the leg the enemy is currently on. It returns a pointer to the next leg of the path when the end of the current leg is reached. The enemy::move() therefore calls the leg::move() like so:

enemy::move()
{
    if( pLeg ) pLeg = pLeg->move(s, x, y);// this keeps pLeg updated. pLeg is a member of the enemy class.
    // other code for frame animation, etc...
}

The parameter 's' is owned by the enemy for its position on the leg and x,y is the enemy position. These are passed by reference to leg::move() so they may be updated.

As an example, a closed oval path with a leg for bringing the enemy on screen would be constructed of 5 legs. The "entry leg" links to the 1st straight leg, which links to the 1st semi-circular leg, which links to the 2nd straight leg, which links to the 2nd semi-circular leg, which links finally back to the 1st straight leg.

This description isn't complete, but I hope it gives you some good ideas.
EDIT: Description of leg::move() code.

[helios]

For the straight line leg it would take both end points as arguments (and assign pLegNext = NULL). For a circular arc leg this ctor takes the start point, center point and the angle through which the leg sweeps.

It's actually better to have "legs" constructed solely of line segments, groups of which can be generated out of curves. For two reasons:
1. Moving a particle along a polygon at a constant rate is far, far easier than along a curve. It's simply vector interpolation. See below for more details.
2. Even if you forgo constant speed, interpolating two vectors is still cheaper than most calculations for curvilinear motion. Especially when in arbitrary angles, trigonometric functions are often involved.

Traversing linked lists is bad for your cache. Since you won't need to remove subpaths, prefer vectors.


Mathy stuff: Let f: R->R^2 be a curve that takes a time t and returns the position (x, y) at which a particle has to be at said time. There exists a function g: R->R such that, if t is a linear function and the particle moves along f(g(t)), the particle moves at a constant rate (i.e. the norm of the derivative of f(g()) is a contant). g is the inverse of the integral of the norm of the derivative of f. This is slightly difficult to calculate.

[D80DSL3A]

helios wrote:

It's actually better to have "legs" constructed solely of line segments, groups of which can be generated out of curves.

I may experiment with this. I wonder how finely I'll have to divide a curve into line segments to obtain motion which looks smoothly curved. The parametrized equations for a line are certainly simple.
For a straight line leg (linLeg, with Leg = abstract base class) I have:

float linLeg::x( float s ){ return x0 + s*tx; }
float linLeg::y( float s ){ return y0 + s*ty; }

where s=distance traveled along the leg and tx and ty = components of the unit tangent vector to the leg.

I actually mis-wrote in my previous post. Leg::move() is defined in the Leg class and is non virtual. It is x(s) and y(s) which are pure virtual in the Leg class.
I am using trig. functions in the equations for a circular leg, eg.

float cirLeg::x( float s )
{
    if( af - a0 > 0.0f )//a0, af = initial and final angles
        return xc + r*cosf( a0 + s/r );// for clockwise motion

    return xc + r*cosf( a0 - s/r );// for ccw motion
}

but I haven't experienced any performance problems (such as high cpu usage. Typical=5%) even when many enemies are in play.

I may be misunderstanding your critique of using std::vector vs a list for leg storage. I am using a vector for storage. By "path is assembled in a linked list fashion" I just mean using a pointer to the next Leg for connecting path segments. No linked list structure is in use. How would traversal of the path in this manner be "bad for your cache"?
Your 'Mathy stuff' did blow me away somewhat even though I think my math skills are fairly strong! I can imagine generating a set of line segments from a function for the curve though.

Thanks for the feedback helios.

[helios]

I wonder how finely I'll have to divide a curve into line segments to obtain motion which looks smoothly curved.

It's theoretically proportional to the norm of the second derivative of the curve. Higher values will require higher concentration of samples. But ultimately you have to try it out and see for yourself. For example, my adaptive Bèzier sampler generated uglier polygons than simple uniform sampling.

I am using trig. functions in the equations for a circular leg, eg. but I haven't experienced any performance problems (such as high cpu usage. Typical=5%) even when many enemies are in play.

You should still avoid them if possible.

By "path is assembled in a linked list fashion" I just mean using a pointer to the next Leg for connecting path segments.

Is the ordering of segments equal to their order in the vector? If so, the extra pointer is redundant. If not, there's no difference between that scheme and a linked list.

[ne555]

> Moving a particle along a polygon at a constant rate is far, far easier than along a curve
¿why do you want constant rate? travelling fast on a sharp turn would look weird

> interpolating two vectors is still cheaper than most calculations for curvilinear motion.
as if interpolating four points would be that costly...

[helios]

¿why do you want constant rate? travelling fast on a sharp turn would look weird

Maybe and maybe not. In any case:
1. Once you have constant speed you can more easily define a speed function over time or space. Otherwise you need to integrate to find out how much distance you've covered.
2. Stitching different curves together without any correction can leave you a particle that changes speeds wildly at the points where the curves connect.

as if interpolating four points would be that costly...

This is a strange argument. Four points times the number of objects that need to be drawn may equal a truckload of operations.

[ne555]

A better argument would have been
>I wonder how finely I'll have to divide a curve into line segments
> to obtain motion which looks smoothly curved.
higher order polynomials would require less division


The two first control points of a bezier would give you the velocity at the start point.
So it should be easy to adjust them to obtain C^1