18 replies to this topic

[bfg.gamepassion]

Hi, i need some advice.

Here's the theory. To an ennemy shoot to the player i must calculate movement of the bullet.

deltax = playerposx - ennemyposx
deltay = playerposy - ennemyposy

angle = atan2(deltax,deltay) // Give me an angle
bulletx=bulletx * cos(angle)
bullety=bullety * sin(angle)

Fist, i know i must precalculate cos and sin table and multiyplys the result by 100.

mvtx = mvtx + cos[angle]
mvty = mvty + sin[angle]
// Approximation (not tested yet)
if (mvtx>=100) bulletx++;mvtx=0;
if (mvtx<=-100) movex--;mvtx=0;
if (mvty>=100) movey++;mvtx=0;
if (mvty<=-100) movey--;mvtx=0;

But, how i calculate the angle in an optimised manner ?

If someone can sen me some advice or a snippet.

Thank you.

[Rybags]

There's much easier ways.

http://en.wikipedia...._line_algorithm

You could use a modified version of the commonly used line draw algorithm to generate the required motion. Rather than executing the loop, you just perform the initial calculations and one iteration each time the bullet has to move.

In Basic you can generally just get away with using the fractional values of the gradient between source/objective. Of course you won't necessarily end up with constant motion for all angles but it's practically unnoticable, e.g. 45 degree motion will generally be quicker than 0 degree motion.

[bfg.gamepassion]

Rybags, on Sat Jul 9, 2011 4:12 AM, said:

There's much easier ways.

http://en.wikipedia...._line_algorithm

You could use a modified version of the commonly used line draw algorithm to generate the required motion. Rather than executing the loop, you just perform the initial calculations and one iteration each time the bullet has to move.

In Basic you can generally just get away with using the fractional values of the gradient between source/objective. Of course you won't necessarily end up with constant motion for all angles but it's practically unnoticable, e.g. 45 degree motion will generally be quicker than 0 degree motion.

Ho yes ! I've forgot bresenham algorithm !!!!!!

Thanks, i'll try that

[Pixelboy]

Rybags, on Sat Jul 9, 2011 4:12 AM, said:

There's much easier ways.

http://en.wikipedia...._line_algorithm

You could use a modified version of the commonly used line draw algorithm to generate the required motion. Rather than executing the loop, you just perform the initial calculations and one iteration each time the bullet has to move.

In Basic you can generally just get away with using the fractional values of the gradient between source/objective. Of course you won't necessarily end up with constant motion for all angles but it's practically unnoticable, e.g. 45 degree motion will generally be quicker than 0 degree motion.

The above pretty much says it all. Don't look at linear movement as a mathematical angle, but rather as a sequence of punctual X and Y offsets that lets you go from point A to point B. You may lose a little precision in the trajectory this way, but it won't be noticeable on a raster screen, especially in a game where many things happen on screen at once.

[bfg.gamepassion]

Pixelboy, on Sat Jul 9, 2011 5:22 AM, said:

Rybags, on Sat Jul 9, 2011 4:12 AM, said:

There's much easier ways.

http://en.wikipedia...._line_algorithm

You could use a modified version of the commonly used line draw algorithm to generate the required motion. Rather than executing the loop, you just perform the initial calculations and one iteration each time the bullet has to move.

In Basic you can generally just get away with using the fractional values of the gradient between source/objective. Of course you won't necessarily end up with constant motion for all angles but it's practically unnoticable, e.g. 45 degree motion will generally be quicker than 0 degree motion.

The above pretty much says it all. Don't look at linear movement as a mathematical angle, but rather as a sequence of punctual X and Y offsets that lets you go from point A to point B. You may lose a little precision in the trajectory this way, but it won't be noticeable on a raster screen, especially in a game where many things happen on screen at once.

I've just try, but it don't really work.

At the creation of the bullet, the destination is player.x,player.y. First my algorithm must not be perfect because the movement is not "linear". But that's not the principal problem, when the bullet is at his destination, an the player is not here anymore, the bullet stop ... and i don't know how to continue the movement in the right direction, at the right angle ...

Edit : And it seems that in must store in memory each point to have the right movement ... And with 1 ko of ram and lot of bullet, it's impossible ...

Edited by bfg.gamepassion, Sat Jul 9, 2011 6:07 AM.

[Pixelboy]

bfg.gamepassion, on Sat Jul 9, 2011 5:56 AM, said:

I've just try, but it don't really work.

At the creation of the bullet, the destination is player.x,player.y. First my algorithm must not be perfect because the movement is not "linear". But that's not the principal problem, when the bullet is at his destination, an the player is not here anymore, the bullet stop ... and i don't know how to continue the movement in the right direction, at the right angle ...

I may have thrown you slightly off-course with the "point A to point B" thing I mentioned. In reality, what you need to calculate is the X and Y offset to apply to the bullet upon each refresh of the screen. You calculate this X and Y offset only once, at the bullet's creation, and apply these offsets repeatedly until the bullet is off the screen.

The level of precision you're looking for in the bullet's linear trajectory may force you to have two X or Y offsets for the same single bullet, alternating between the two sets of offsets, in an effort to keep the bullet as close as possible to an imaginary straight line. You'll need to do a few tests and see where it takes you.

[Rybags]

The bullet doesn't need to stop.

With the Bresenham method, remove the end of loop condition test and just keep doing the other parts, use edge of screen or collision or whatever as the stop condition.

So in effect you don't need the loop (or simulated loop) at all.

What's important is that you're just using the DeltaX/DeltaY method where you add that calculated gradient and do the compare as a condition each time as to whether the minor slope changes.

[Bruce Tomlin]

You probably should learn about this if you don't already understand it:

http://en.wikipedia....oint_arithmetic

So if you determine that for every 1.0 movement of X, you want a 1.5 movement of Y, using an 8.8 fixed point number, you would store your Y position as a 16-bit number, with the Y value in the high byte and remainder in the low byte. The Y offset would then be 0x0180 in hex. So your Y value would be 0x0000, 0x0180, 0x0300, 0x0480, 0x0600, which translate to 0.0, 1.5, 3.0, 4.5, and 6.0.

[PkK]

There's some fixed-point trigonometry functions in my libcvu library at
http://colecovision....ent/libcv.shtml
have a look at the cvu_f header in there.

Philipp

[bfg.gamepassion]

Ok, this the solution i've used.

I considered x movement move by 1 pixel. So at the creation of the bullet I initialise 2 variables :

first : The bullet/object start position y << 6 for avoid float
ennemyObj[eo].gi1 = y<<6;

second the y movement increment << 6 for avoid float
ennemyObj[eo].gi2 = ((sprites[PLAYER_SPRITE1].y+8 - y) <<6 / ((sprites[PLAYER_SPRITE1].x+8 - x) << 6));

Then i move the bullet like that :

(*sx) ++; // Increment sprite position x by one
(*eo_gi1) += (*eo_gi2); // Increment object position y by calculated increment
(*sy) = (*eo_gi1)>>6; // Transform position y object in position y sprite

And it works not bad at all. I must arrange the random ennemy appaering and i'll post a video in the right topic.

Thanks for all your advices, and for the previous post, i'll look at your librarie, it may interest me a lot !!

Thanks again !

[GroovyBee]

bfg.gamepassion, on Tue Jul 12, 2011 6:51 AM, said:

second the y movement increment << 6 for avoid float
ennemyObj[eo].gi2 = ((sprites[PLAYER_SPRITE1].y+8 - y) <<6 / ((sprites[PLAYER_SPRITE1].x+8 - x) << 6));

Are you sure that this shouldn't be :-

ennemyObj[eo].gi2 = ((sprites[PLAYER_SPRITE1].y+8 - y) <<6) / (sprites[PLAYER_SPRITE1].x+8 - x);

You might also find that creating a pointer to &ennemyObj[eo] and using syntax like :-

pEnemy->gi2=

Produces faster and more compact code. However these sort of optimisations are compiler dependent. Have a look at the assembly language produced in each case.

[bfg.gamepassion]

GroovyBee, on Tue Jul 12, 2011 7:19 AM, said:

bfg.gamepassion, on Tue Jul 12, 2011 6:51 AM, said:

second the y movement increment << 6 for avoid float
ennemyObj[eo].gi2 = ((sprites[PLAYER_SPRITE1].y+8 - y) <<6 / ((sprites[PLAYER_SPRITE1].x+8 - x) << 6));

Are you sure that this shouldn't be :-

ennemyObj[eo].gi2 = ((sprites[PLAYER_SPRITE1].y+8 - y) <<6) / (sprites[PLAYER_SPRITE1].x+8 - x);

You might also find that creating a pointer to &ennemyObj[eo] and using syntax like :-

pEnemy->gi2=

Produces faster and more compact code. However these sort of optimisations are compiler dependent. Have a look at the assembly language produced in each case.

No, all the "delta" must be <<6. And if you put <<6 at all the formula ((sprites[PLAYER_SPRITE1].y+8 - y) / (sprites[PLAYER_SPRITE1].x+8 - x) << 6 , the program return 0 or 1. Seems that the division convertion don't work well ... (Hard to explain in english nmy not born langage).

[GroovyBee]

This :-

bfg.gamepassion, on Tue Jul 12, 2011 7:23 AM, said:

((sprites[PLAYER_SPRITE1].y+8 - y) / (sprites[PLAYER_SPRITE1].x+8 - x) << 6

Is not the same as this :-

ennemyObj[eo].gi2 = ((sprites[PLAYER_SPRITE1].y+8 - y) <<6) / (sprites[PLAYER_SPRITE1].x+8 - x);

In my version the scaling is done before the division and in your version it is done afterwards.

If all you want is x and y deltas then I suspect that it is going to be much quicker to do a series of if/then/else than it is to "call" the divide routine in the compiler's library and do multiple shifts.

e.g.

signed char enemyBulletDeltaX=-1;
signed char enemyBulletDeltaY=-1;

if (enemyX<playerX)
    enemyBulletDeltaX=1;
else if (enemyX==playerX)
    enemyBulletDeltaX=0;

if (enemyY<playerY)
   enemyBulletDeltaY=1;
else if (enemyY==playerY)
   enemyBulletDeltaY=0;

And using this code you don't need to handle 16bit quantities either. The only negative is the fact that you only get bullet movement in 8 compass directions.

[bfg.gamepassion]

GroovyBee, on Tue Jul 12, 2011 7:55 AM, said:

This :-

bfg.gamepassion, on Tue Jul 12, 2011 7:23 AM, said:

((sprites[PLAYER_SPRITE1].y+8 - y) / (sprites[PLAYER_SPRITE1].x+8 - x) << 6

Is not the same as this :-

ennemyObj[eo].gi2 = ((sprites[PLAYER_SPRITE1].y+8 - y) <<6) / (sprites[PLAYER_SPRITE1].x+8 - x);

In my version the scaling is done before the division and in your version it is done afterwards.

If all you want is x and y deltas then I suspect that it is going to be much quicker to do a series of if/then/else than it is to "call" the divide routine in the compiler's library and do multiple shifts.

e.g.

signed char enemyBulletDeltaX=-1;
signed char enemyBulletDeltaY=-1;

if (enemyX<playerX)
    enemyBulletDeltaX=1;
else if (enemyX==playerX)
    enemyBulletDeltaX=0;

if (enemyY<playerY)
   enemyBulletDeltaY=1;
else if (enemyY==playerY)
   enemyBulletDeltaY=0;

And using this code you don't need to handle 16bit quantities either. The only negative is the fact that you only get bullet movement in 8 compass directions.

Yes, and that's the thing i don't want, only 8 directions

[newcoleco]

OFFTOPIC : Nice you passed by at the video chat during the ADAMCon meeting.. you just missed the presentation by Jim N. he talked about Commando Return and all the new games around.

[bfg.gamepassion]

newcoleco, on Sat Jul 16, 2011 1:43 PM, said:

OFFTOPIC : Nice you passed by at the video chat during the ADAMCon meeting.. you just missed the presentation by Jim N. he talked about Commando Return and all the new games around.

Hélas je n'avais pas beaucoup de temps, j'ai quelquepeut suivit ce que racontait opcode, c'était plutôt interessant. En tout cas le système de chat video est une tres bonne idée !!

[nanochess]

Rybags, on Sat Jul 9, 2011 7:03 AM, said:

The bullet doesn't need to stop.

With the Bresenham method, remove the end of loop condition test and just keep doing the other parts, use edge of screen or collision or whatever as the stop condition.

So in effect you don't need the loop (or simulated loop) at all.

What's important is that you're just using the DeltaX/DeltaY method where you add that calculated gradient and do the compare as a condition each time as to whether the minor slope changes.

That's a pretty good idea

[hardhat]

Here is a working example of using the Bresenham's Line Algorithm to control bullets. You move your ship around on the screen, and the ship in the centre of the screen continually shoots towards your position at the time.

#include <string.h>
#include <coleco.h>
#include <getput1.h>

#define MAXBULLET 8
struct Bullet {
	byte flags;
	byte sprite;
	byte dx,dy;
	int err;
} bullet[MAXBULLET];
#define BUL_ACTIVE 0x80
#define BUL_UP 0x1
#define BUL_LEFT 0x2

void updatebullet(int id)
{
	byte s=bullet[id].sprite;
	byte dx=bullet[id].dx;
	byte dy=bullet[id].dy;
	int e2;

	if((bullet[id].flags&BUL_ACTIVE)==0) return; // not active.

	if(sprites[s].x==255 || sprites[s].x==0 || sprites[s].y==0 || sprites[s].y==191) {
		bullet[id].flags=0; // sprite inactive.
		sprites[s].y=192; // off screen.
	}
	e2=bullet[id].err<<1;
	if( e2 > -dy) {
		bullet[id].err-=dy;
		sprites[s].x+=(bullet[id].flags&BUL_LEFT)?-1:1;
	}
	if( e2 < dx ) {
		bullet[id].err+=dx;
		sprites[s].y+=(bullet[id].flags&BUL_UP)?-1:1;
	}
}

int newsprite(int id,int x0,int y0)
{
	const int reserved=2;
	sprites[id+reserved].x=x0;	// reserve first two sprites for player and enemy.
	sprites[id+reserved].y=y0;
	sprites[id+reserved].pattern=8;  // Our bullet pattern
	sprites[id+reserved].colour=15;	// VDP_WHITE
	return id+reserved;
}

int newbullet(int x0,int y0,int x1,int y1)
{
	int i;
	for(i=0;i<MAXBULLET;i++) {
		if(bullet[i].flags&BUL_ACTIVE) continue;
		/* found an unused bullet, so let's set it up.*/
		bullet[i].sprite=newsprite(i,x0,y0);
		bullet[i].flags=BUL_ACTIVE;
		bullet[i].flags|=(x0<x1)?0:BUL_LEFT;
		bullet[i].flags|=(y0<y1)?0:BUL_UP;
		bullet[i].dx=(x0<x1)?x1-x0:x0-x1;
		bullet[i].dy=(y0<y1)?y1-y0:y0-y1;
		bullet[i].err=bullet[i].dx-bullet[i].dy;
		return i;
	}
	return 0;	// all bullets still active.
}

const byte shipsPat[]={
	0x0f,0x1f,0x3f,0xff,0xff,0x3f,0x1f,0x0f,
	0x0f,0x1f,0x3f,0xff,0xff,0x3f,0x1f,0x0f,
	0xf0,0xf8,0xfc,0xff,0xff,0xfc,0xf8,0xf0,
	0xf0,0xf8,0xfc,0xff,0xff,0xfc,0xf8,0xf0,

	0x10,0x30,0xc3,0xcf,0xcf,0x3c,0x30,0x10,
	0x10,0x30,0xc3,0xcf,0xcf,0x3c,0x30,0x10,
	0x08,0x0c,0xc3,0xf3,0xf3,0x3c,0x0c,0x08,
	0x08,0x0c,0xc3,0xf3,0xf3,0x3c,0x0c,0x08,

	0x60,0xd0,0xf0,0x60,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
};

void main()
{
	int i;
	int frame=0;

	screen_mode_1_text();
	sprites_16x16();
	change_spattern(0,shipsPat,3*4);
	sprites[0].x=128;
	sprites[0].y=96;
	sprites[0].pattern=0;
	sprites[0].colour=11;
	sprites[1].x=192;
	sprites[1].y=64;
	sprites[1].pattern=4;
	sprites[1].colour=13;
	for(i=2;i<32;i++) sprites[i].y=0xd0;
	updatesprites(0,12);
	fill_color(0,0x61,255);
	load_ascii();
	cls();
	screen_on();
	print_at(2,0,"Stop, or I'll say stop again!");

	for(;;) {
		enable_nmi();
		delay(1);
		for(i=0;i<MAXBULLET;i++) {
			updatebullet(i);
			updatebullet(i);	// 2 pixels per 60th.
		}
		if((frame&15)==0) newbullet(sprites[0].x+8,sprites[0].y+8,sprites[1].x+8,sprites[1].y+8);
		frame++;
		disable_nmi();

		// user to dodge the bullets.
		if(joypad_1&LEFT) sprites[1].x--;
		if(joypad_1&RIGHT) sprites[1].x++;
		if(joypad_1&UP) sprites[1].y--;
		if(joypad_1&DOWN) sprites[1].y++;

		// draw the effects.
		updatesprites(0,12);
	}
}

void nmi()
{
	;
}

The interesting part is newBullet and updateBullet.

In newBullet, the start position for the sprite, and the current location of the target are passed in. It finds an unused struct Bullet entry and fills it out. The line is drawn in one of 8 directions, and the flags are set according to whether it is moving up or down, and whether it is moving left or right.

Update bullet just implements the optimized description of Bresenham's Line algorithm plus checks that the bullet is active, and kills a bullet when it goes off screen.

It should be pretty straight forward to put this kind of thing in your own game if you like.

Attached Thumbnails

• 

Attached Files

•  bresshot.zip   4.38K   23 downloads

Edited by hardhat, Sat Dec 31, 2011 3:46 PM.

[bfg.gamepassion]

hardhat, on Sat Dec 31, 2011 2:58 PM, said:

Here is a working example of using the Bresenham's Line Algorithm to control bullets. You move your ship around on the screen, and the ship in the centre of the screen continually shoots towards your position at the time.

#include <string.h>
#include <coleco.h>
#include <getput1.h>

#define MAXBULLET 8
struct Bullet {
	byte flags;
	byte sprite;
	byte dx,dy;
	int err;
} bullet[MAXBULLET];
#define BUL_ACTIVE 0x80
#define BUL_UP 0x1
#define BUL_LEFT 0x2

void updatebullet(int id)
{
	byte s=bullet[id].sprite;
	byte dx=bullet[id].dx;
	byte dy=bullet[id].dy;
	int e2;

	if((bullet[id].flags&BUL_ACTIVE)==0) return; // not active.

	if(sprites[s].x==255 || sprites[s].x==0 || sprites[s].y==0 || sprites[s].y==191) {
		bullet[id].flags=0; // sprite inactive.
		sprites[s].y=192; // off screen.
	}
	e2=bullet[id].err<<1;
	if( e2 > -dy) {
		bullet[id].err-=dy;
		sprites[s].x+=(bullet[id].flags&BUL_LEFT)?-1:1;
	}
	if( e2 < dx ) {
		bullet[id].err+=dx;
		sprites[s].y+=(bullet[id].flags&BUL_UP)?-1:1;
	}
}

int newsprite(int id,int x0,int y0)
{
	const int reserved=2;
	sprites[id+reserved].x=x0;	// reserve first two sprites for player and enemy.
	sprites[id+reserved].y=y0;
	sprites[id+reserved].pattern=8;  // Our bullet pattern
	sprites[id+reserved].colour=15;	// VDP_WHITE
	return id+reserved;
}

int newbullet(int x0,int y0,int x1,int y1)
{
	int i;
	for(i=0;i<MAXBULLET;i++) {
		if(bullet[i].flags&BUL_ACTIVE) continue;
		/* found an unused bullet, so let's set it up.*/
		bullet[i].sprite=newsprite(i,x0,y0);
		bullet[i].flags=BUL_ACTIVE;
		bullet[i].flags|=(x0<x1)?0:BUL_LEFT;
		bullet[i].flags|=(y0<y1)?0:BUL_UP;
		bullet[i].dx=(x0<x1)?x1-x0:x0-x1;
		bullet[i].dy=(y0<y1)?y1-y0:y0-y1;
		bullet[i].err=bullet[i].dx-bullet[i].dy;
		return i;
	}
	return 0;	// all bullets still active.
}

const byte shipsPat[]={
	0x0f,0x1f,0x3f,0xff,0xff,0x3f,0x1f,0x0f,
	0x0f,0x1f,0x3f,0xff,0xff,0x3f,0x1f,0x0f,
	0xf0,0xf8,0xfc,0xff,0xff,0xfc,0xf8,0xf0,
	0xf0,0xf8,0xfc,0xff,0xff,0xfc,0xf8,0xf0,

	0x10,0x30,0xc3,0xcf,0xcf,0x3c,0x30,0x10,
	0x10,0x30,0xc3,0xcf,0xcf,0x3c,0x30,0x10,
	0x08,0x0c,0xc3,0xf3,0xf3,0x3c,0x0c,0x08,
	0x08,0x0c,0xc3,0xf3,0xf3,0x3c,0x0c,0x08,

	0x60,0xd0,0xf0,0x60,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,
};

void main()
{
	int i;
	int frame=0;

	screen_mode_1_text();
	sprites_16x16();
	change_spattern(0,shipsPat,3*4);
	sprites[0].x=128;
	sprites[0].y=96;
	sprites[0].pattern=0;
	sprites[0].colour=11;
	sprites[1].x=192;
	sprites[1].y=64;
	sprites[1].pattern=4;
	sprites[1].colour=13;
	for(i=2;i<32;i++) sprites[i].y=0xd0;
	updatesprites(0,12);
	fill_color(0,0x61,255);
	load_ascii();
	cls();
	screen_on();
	print_at(2,0,"Stop, or I'll say stop again!");

	for(;;) {
		enable_nmi();
		delay(1);
		for(i=0;i<MAXBULLET;i++) {
			updatebullet(i);
			updatebullet(i);	// 2 pixels per 60th.
		}
		if((frame&15)==0) newbullet(sprites[0].x+8,sprites[0].y+8,sprites[1].x+8,sprites[1].y+8);
		frame++;
		disable_nmi();

		// user to dodge the bullets.
		if(joypad_1&LEFT) sprites[1].x--;
		if(joypad_1&RIGHT) sprites[1].x++;
		if(joypad_1&UP) sprites[1].y--;
		if(joypad_1&DOWN) sprites[1].y++;

		// draw the effects.
		updatesprites(0,12);
	}
}

void nmi()
{
	;
}

The interesting part is newBullet and updateBullet.

In newBullet, the start position for the sprite, and the current location of the target are passed in. It finds an unused struct Bullet entry and fills it out. The line is drawn in one of 8 directions, and the flags are set according to whether it is moving up or down, and whether it is moving left or right.

Update bullet just implements the optimized description of Bresenham's Line algorithm plus checks that the bullet is active, and kills a bullet when it goes off screen.

It should be pretty straight forward to put this kind of thing in your own game if you like.

Ho my god !!! That's a sample code ! Thanks a lot, i'll check that, and implement it in my new game, because i need that thing !!! Thanks VERY VERY MUCH !!