Jump to content
Eternal Lands Official Forums
_alias

Missiles

Recommended Posts

It is something reletively easy to copy (google it to find some code), but it is something reletively easy to write.

All the modern 2d line drawing uses it so it is easy to find. don't ask me how to write it i failed computer graphics.

 

First you calculate a fiew constants, then there are 8 possible cases (0<45,45<90 etc) and then you just have a for loop that moves ether x+1 or x+1,y+1 for example (second case), the loops differ from for loops with x/y, and incrementing/decrementing in x/y.

you would put a check(x,y) to check if there is a map object, a person/monster blocking.

You might want to ignore actors these as the arrow might just graze the tile.

you might want to do further processing to see how much of the tile it goes over wether it goes straight over or just goes over a small corner.

with the way the game is structured it might be best (atleast at first) ignore collisions with most small map objects and only have it have collisions with walls and houses.

 

One thing that you should do is have arrows (or any other ammo like bullets for guns) take up an equip slot to allow for different types of ammo, with different qualities (range, damage, cost)

It would make sence to have a quiver (maybe an item required to store arrows or something automatic when you pick an arrow up) atleast as an icon to represent arrows and maybe 3d object on the person?

 

I'll try and work on the code tonight, i have written it in java not c and it has been a while but it should be reletively easy to do but i would recomend you find and copy someone elses code and replace paint with a check tile function.

Share this post


Link to post
Share on other sites

Wow, sounds so easy.

Perhaps you could elaborate on

you would put a check(x,y) to check if there is a map object, a person/monster blocking.

Share this post


Link to post
Share on other sites

Somehow it would look funny, if an arrow flying at a height of 10 meters just hits an innocent wood sprite on one of the tiles of the arrows path.

 

Piper

Share this post


Link to post
Share on other sites
Somehow it would look funny, if an arrow flying at a height of 10 meters just hits an innocent wood sprite on one of the tiles of the arrows path.

 

It would be relatively simple to give the arrow a simple z-axis profile as well; this would not be part of the bresenham algorithm, but passed to the callback evaluated for each traversed square.

 

This callback would be given the location (x,y), height (z), and an error term (0 if the line passes through the centre of the square, going to 1 if it just clips a corner). The callback would evaluate whether there is anything to hit, and whether the archer accidentally hits it (factor in: z, error, and skill).

 

I guess that if the archer misses their intended target, the arrow could continue in flight until z<ground level. Possibly hitting other bystanders...

Share this post


Link to post
Share on other sites

Well you would need to check the tiles in the path of the arrow each tile, instead of painting you call a check method, in this you would check for anything that might block the arrow.

The things that i can think of is:

1. 3d objects on the map, but you probly want to allow short objects like bushes and maybe thin trees so you may need to decide what objects the arrow can pass through and what they cannot. i' don't know enough about the map files and how they are stored, would it be hard to create a flag on some tiles to specify if arrows will be blocked by the tile? should this be related to the 3d object and cross referenced with the tile?

 

2. actors (people and monsters) which are in the path, so you need to check the list of actors. i'm not shure how the server is designed, are actors stored in an array or a list that is processed, ether way you just need to determine if anyone is in the way and could be cought in the crossfire. you will need to decide what happens with these collisions, does the person in the way get the damage? (need to check for pk map and multiplay maps) does the attack not work? (ie an error says someone is in the way), does the arrow fly over the person?, does flying over head matter what size the actor is? (an advantage of gnomes and bunnies?)

Share this post


Link to post
Share on other sites

My C is about 7 years rusty, but I couldn't resist:

 

I don't have a C compiler set up, so you'll have to bear with my stupid mistakes, and I did not use ANSI C standards in my declarations, but here's a translation from the wikipedia page. Cool algorithm.

 


#include math.h

struct vector {int x; int y}


void Bresenham(vector start, vector finish)
{
int x0=start.x;
int x1=finish.x;

int y0=start.y;
int y1=finish.y;
boolean steep=(abs(x0-x1)>abs(y0-y1));

if steep
{
 swap (x0,y0);
 swap (x1,y1);
}

if x1>x2 
{
	swap (x0,x1);
	swap (y0,y1);
}

float slope = (abs(x0-x1)/abs(y0-y1));
int deviation=0;

int currentY=start.y;
for (int i=start.x;i<=finish.x;i++)
{

  if steep
  {
  // Ent, you'll need to determine how this function works for you

  }
  else
  {
  // Ent, you'll need to determine how this function works for you
	 	doStuffThatNeedsDoneAtThisPosition(i,currentY);		
  }

  devation=devation+slope;
  if deviation>.5
  {
	y++;
	error-=1;	
  }

}
}

void swap(int num1, int num2)
{
int holder;
holder=num1;
num1=num2;
num2=holder;
}

 

 

 

So, I took it a step further. This is a version that returns an array of vectors (the gridded course) including a z axis. The z handling is a skeleton. It should probably incorporate z from the start and finish vectors to help negotiate ascent and descent. In fact, the basic idea of the Bresenham algorithm could be used to calculate the z at each grid point between start and halfway, and halfway nad finish. It also works on the assumption that the Z axis increases at an arc of 1 z-grid every 5 grid distance, and descends at the same rate.

 

#include math.h

struct vector {int x; int y; int z}


vector * Bresenham(vector start, vector finish)
{
vector * retval; 
int x0=start.x;
int x1=finish.x;


int y0=start.y;
int y1=finish.y;
boolean steep=(abs(x0-x1)>abs(y0-y1));

if steep
{
 swap (x0,y0);
 swap (x1,y1);
}

if x1>x2 
{
	swap (x0,x1);
	swap (y0,y1);
}

float slope = (abs(x0-x1)/abs(y0-y1));
int deviation=0;
s maxDistance=abs(x0-x1);
retarr = new vector[maxdist];
int currentY=start.y;
int counter=0;
int zdelta=1;
int halfway=(maxdist/2)
int z=1;

for (int i=start.x;i<=finish.x;i++)
{
  if counter>halfway
  {
   zdelta=-1;
  }

  if counter%5 =0 z+=zdelta;

  if steep
  {
		retarr[counter].x=currentY;
	retarr[counter].y=i;

  }
  else
  {
	retarr[counter].x=i;
	retarr[counter].y=currentY;
  }

  retarr[counter].z = z; 

  devation=devation+slope;
  if deviation>.5
  {
	y++;
	error-=1;	
  }
  counter++;
}

 return retarr;
}

void swap(int num1, int num2)
{
int holder;
holder=num1;
num1=num2;
num2=holder;
}

 

 

Just realized the flaw in my programming. Technically, an arrow flies in a parabolic arc. If velocity >>>> distance, this can be represented as I represented it, but this might look funny at great distances/great heights where you would expect an elegant shot in the form of an arc.

Edited by Kalach

Share this post


Link to post
Share on other sites

Nice attempt Kalach, but that code won't work, even if the C syntax is fixed. That aside...

 

For our purposes, we cannot use the stock bresenham algorithm: It is only concerned with finding the points along the line, and not in the direction of traversal.

 

As you can see from the algorithm, it only actually solves for gradients 0 to 45°, and gets the rest of the range by flipping and swapping end points.

 

For missile trajectories, we have a definite direction.

 

We need a modified algorithm which always traverses the path from start to finish. Not as efficient as bresenham, but still reasonable cheap.

Share this post


Link to post
Share on other sites

Nice attempt Kalach, but that code won't work, even if the C syntax is fixed. That aside...

 

For our purposes, we cannot use the stock bresenham algorithm: It is only concerned with finding the points along the line, and not in the direction of traversal.

 

As you can see from the algorithm, it only actually solves for gradients 0 to 45°, and gets the rest of the range by flipping and swapping end points.

 

For missile trajectories, we have a definite direction.

 

We need a modified algorithm which always traverses the path from start to finish. Not as efficient as bresenham, but still reasonable cheap.

 

 

Reread your post and I got it the second time. The problem with the function as it's written is that it may end up going the wrong direction. Note that the swapping of X and Y will not be a problem, because the setting of the coordinates is swapped back. The other problem seems trivial to fix, I think...

 

 


vector * Bresenham(vector start, vector finish, vector& retarr[])
{

int x0=start.x;
int x1=finish.x;

boolean reverse=0;	
int y0=start.y;
int y1=finish.y;
boolean steep=(abs(x0-x1)>abs(y0-y1));

if steep
{
 swap (x0,y0);
 swap (x1,y1);
}

if x1>x2 
{
	swap (x0,x1);
	swap (y0,y1);
	s reverse=1;
}

float slope = (abs(x0-x1)/abs(y0-y1));
int deviation=0;
maxDistance=abs(x0-x1);
retarr = new vector[maxdist];
int currentY=start.y;
int counter=0;
int zdelta=1;
int halfway=(maxdist/2)
int z=1;
int index;

for (int i=start.x;i<=finish.x;i++)
{
  if counter>halfway
  {
   zdelta=-1;
  }

  if counter%5 =0 z+=zdelta;
  index=counter;
  if reverse index=maxDistance-counter;

  if steep
  {
		retarr[index].x=currentY;
	retarr[index].y=i;

  }
  else
  {
	retarr[index].x=i;
	retarr[index].y=currentY;
  }

  retarr[counter].z = z; 

  devation=devation+slope;
  if deviation>.5
  {
	y++;
	error-=1;	
  }
  counter++;
}

 return retarr;
}

 

So now, the array will have all of the points traversed in order, (retArr[0]=vector for first point).

 

A question comes up, assuming the arrow is not stopped before reaching it's target, is it necessarily stopped at it's target? This could be modified to use counter to drive the loop, going from starting point through finishing point until it reaches the maximum distance or Z=0;

 

 

2nd edit:

 

Oh yeah... new with arrays is a C++ concept, not a C concept. I told you it'd been 6 years. :hug::icon13: I'm changing the code to let the array be initalized outside, as I am not familiar with C memory allocaiton. :icon13::wub::wub::wacko::hug:

Edited by Kalach

Share this post


Link to post
Share on other sites

Bresenham will find the points on the line between start and finish, but may find them in either direction, depending on the gradient -- notice the second block of 'swap()' calls in your implementation.

 

For each step we are evaluating some callback function, to see if we hit an obsticle. As soon as we hit something we have finished.

 

But with bresenham, half the trajectories will be evaluated from finish to start (due to end point swapping). This doesnt matter for line drawing, but does matter for the missile trajectory, since we would be evaluating obsticles in the wrong order.

 

This would result in hitting a bystander on the other side of a wall, since the collision with the bystander would be evaluated before that with the wall.

 

 

The end point is another issue: We don't actually have a definite end point, just a target (which is an actor or object with a coordinate). If the missile misses the target, then it could continue on. If it can hit a bystander standing between archer and target, then it could equally hit a bystander beyond the target if the archer misses.

 

This is where the z-axis trajectory becomes important; the callback should first test whether the missiles z coordinate is above the ground level; if not then it has bit dust.

 

 

UPDATE...

 

What it boils down to, is that it would be far simpler to just implement a naive algorithm. In sketchy pseudocode:

missile_trajectory (point start, point finish, collision_fn eval)
{
point current;
point dv = (finish - start) / length (finish - start)

for (current = start + dv; eval (current); current += dv);
}

(This does not include zaxis, which is essential, and assumes that the target id is known to eval()).

Edited by trollson

Share this post


Link to post
Share on other sites

Bresenham will find the points on the line between start and finish, but may find them in either direction, depending on the gradient -- notice the second block of 'swap()' calls in your implementation.

 

For each step we are evaluating some callback function, to see if we hit an obsticle. As soon as we hit something we have finished.

 

But with bresenham, half the trajectories will be evaluated from finish to start (due to end point swapping). This doesnt matter for line drawing, but does matter for the missile trajectory, since we would be evaluating obsticles in the wrong order.

 

This would result in hitting a bystander on the other side of a wall, since the collision with the bystander would be evaluated before that with the wall.

 

 

The end point is another issue: We don't actually have a definite end point, just a target (which is an actor or object with a coordinate). If the missile misses the target, then it could continue on. If it can hit a bystander standing between archer and target, then it could equally hit a bystander beyond the target if the archer misses.

 

This is where the z-axis trajectory becomes important; the callback should first test whether the missiles z coordinate is above the ground level; if not then it has bit dust.

 

It is dangerous when arrows and bolts start flying around...

 

We crossed posts. See changes above. And yes, it will have to be changed to a counter driven loop. I can make that adjustment later.

 

The idea being that we use this lightweight function to generate the path array, and then we traverse the array to check for collisions, instead of attempting to check for path collisions while we do the generation. Does that make sense?

Share this post


Link to post
Share on other sites

And, while following the line, you will have to be checking for collisions with map objects to see if you hit a wall or tree, and you need to take into account the odd shapes of objects, and remember that many items are much larger or much smaller then a square (light poles, ship sales, huge tree trunks).

Share this post


Link to post
Share on other sites

More crossed posts... :icon13:

 

The array is unnecessary if we always traverse in the right direction. Bresenham is optimised for a particular role, and by the time we've 'fixed' it to do what we want, its lost its original advantage.

 

Array is extra overhead, and we are now doing a double pass through. Better to just use the naive algorithm and take advantage of early exit conditions.

Edited by trollson

Share this post


Link to post
Share on other sites

More crossed posts... :icon13:

 

The array is unnecessary if we always traverse in the right direction. Bresenham is optimised for a particular role, and by the time we've 'fixed' it to do what we want, its lost its original advantage.

 

Array is extra overhead, and we are now doing a double pass through. Better to just use the naive algorithm and take advantage of early exit conditions.

 

 

So why didn't we decide to use the naive algorithm to start with?

Share this post


Link to post
Share on other sites

UPDATE...

 

What it boils down to, is that it would be far simpler to just implement a naive algorithm. In sketchy pseudocode:

missile_trajectory (point start, point finish, collision_fn eval)
{
point current;
point dv = (finish - start) / length (finish - start)

for (current = start + dv; eval (current); current += dv);
}

(This does not include zaxis, which is essential, and assumes that the target id is known to eval()).

 

There's so much left out of here, it's difficult for me to see where the efficiency gain would be. I suppose it's somewhere in one of the abstracted functions? :icon13:

Share this post


Link to post
Share on other sites

I wouldve just implemented a sketchy algorithm (straight line raycasting?) that checks if the missile would hit anything before you fire. Then if it was gonna hit something, put a message saying "target is not in line of sight" or something...

Is it really that important that we have missiles flying over fences? I think we should just implement a basic method first see how it works...

Share this post


Link to post
Share on other sites

It will be a lot more fun if it can be done right using the 3d object's boudning boxes. So I think it is important, alias.

 

I was even thinking about possibly making a different viewport-window, like a first person view game that just shows the hand with the bow in it. You'd have to go into "missle mode" to be able to shoot. it's probably a stupid idea for this game but i thought i'd say it nonetheless :D

Share this post


Link to post
Share on other sites

Very interesting thread.

 

Is it really that important that we have missiles flying over fences? I think we should just implement a basic method first see how it works...

 

I think it could be done working great without adding a z high factor that i think _alias is talking about.

Edited by Gravito

Share this post


Link to post
Share on other sites

Personally i would just ignore 3d and process it from a quick check of what is in the tiles in the path.

Generally the maps have thair 3d objects spread out and it would be really difficult for the server to use any 3d processing without useing an awful lot of extra processing power. Instead just working with an array of objects (and actors) that might block is far easyer for the server to process. if you really want to you could possibly do some further processing to check to see if there is still a collision for objects not sitting exactly in the center of the tile but it is probly not worth it.

 

Maybe you could have a layer that specifies the likely hood of the arrow passing through the object, so if someone is behind a tree they may have a 20% chance of being hit where if they stand behind a building they cannot be hit (or whatever you decide).

Share this post


Link to post
Share on other sites

If we are going to implement them, they will be implemented properly, not using shitty ways such as ignoring 3d objects and the Z dimension.

Share this post


Link to post
Share on other sites

missile_trajectory (point start, point finish, collision_fn eval)
{
 point current;
 point dv = (finish - start) / length (finish - start)

 for (current = start + dv; eval (current); current += dv);
}

Couple of additional notes that need to be made:

  • 'point' is a float position (obviously). It may be (x,y), or (x,y,z).
     
  • To ensure that each 'current' is a different position (when rounded), 'length()' should return the maximum of the absolute dimensions (eg, length ((point){1,-3,2}) is 3). If we want to resolve to (x,y) map locations, then length() should also ignore the z-dimension.
     
  • The 'eval()' does everything else, should return true if the missile trajectory has ended, and should resolve the end effects. It would have to know about any other information (target id, map information, etc). Efficient design here is essential. In practive, other parameters will be passed in (results of a z-offset, state information etc).

There's so much left out of here, it's difficult for me to see where the efficiency gain would be. I suppose it's somewhere in one of the abstracted functions? :(

 

Yes, since we need to evaluate something at each position traversed in order, there is little more we can do with the line-finding algorithm. Its the 'eval()' visitor/callback which needs to be as efficient as possible, in determining if the missile passes through the location.

 

The client only needs to be told that the missile starts from object A at point P1 and ends at object B at point P2 (as determined by eval(), which may not be the original target), and to animate accordingly.

 

We don't have to be overly accurate in the precise path that the missile takes. There is a lot of 'fuzz' in the model -- from the limited graphical representation, the skill of the bowman , etc. The missile could go short or long, or wide -- in which case it could hit a target not in the direct line of sight between shooter and target. Though this last case could be worked by an initial skill check and adding an error to the target location.

 

Additional: Is it worth modelling the z-axis profile as anything other than a straight line? If targets cannot be selected if they are out of visual range, over which trajectories are effectively flat (or rather, are flat enough that it would not be worth the effort of calculating the z-axis profile).

 

Archers could select a 45°+ launch (cf. mortar trajectory), to shoot over any intervening obsticles (and bypass all the line traversing stuff), but this would require a very high level of skill (and different animation). This option would not availble to slings or crossbows though (1), which are both flat trajectories (if you actually want to hit anything).

 

(1) Slings are very high skill, very low tech; crossbows are low skill, high (medieval) tech. Bows sitting inbetween. The progression is not one of increasing performance, but in a shift in emphasis from skill to industry, which continues with the introduction of firearms. It is cheaper to stockpile weapons and give them to quickly trained peasants, rather than maintain proficient soldiers.

Edited by trollson

Share this post


Link to post
Share on other sites

What we have problems with right now is finding a FAST algorithm for 3d collision detection. The rest is relatively easy.

Share this post


Link to post
Share on other sites
What we have problems with right now is finding a FAST algorithm for 3d collision detection.

 

Don't even try to implement a real, accurate, collision algorithm; an approximate, statistical based one would give the same user experience. The game (in common with most RPGs) is based on statisical models (skills and random numbers).

 

Consider how many unknowns there are from the player's perspective -- they just click on their intended target, and a moment later a missile is animated going from their character to some other object (target or not). This animation would be quick, and out of necessessity need not be the same route as the server checked for (in the case of moving targets).

 

I was going to suggest just treating objects as bounding boxes around a gaussian blob; but for the this type of application, simply assigning an 'obscuration factor' to objects with a presence in a traversed square *, assessed against the characters skill plus offset, would do just as well.

 

* for static objects, this would be precalculated for each map. So seperate the checks for collision with static objects (quick), and with collision with avatars (either targetted, +skill, or accidental, -skill).

Some additional thoughts from a lunchtime walk-in-the-woods (2006-06-06):

  • Static information about each square could be divided into three types, which cover most effects I can think of:

  1. Obsticle
    -- representing a hard target which would stop the missile, and measured as a challenge against the shooter's skill.
    Eg, a table. wall, tree.


  2. Absorption
    -- representing a soft target that will reduce damage from the missile, measured as a damage reduction and (optionally) a skill challenge to avoid.
    Eg, firing through curtains, tall grass, tree folage.


  3. Obscuration
    -- representing something obscuring the shooter's view of the target, and acting as a skill reduction for the rest of the trajectory.
    Eg, firing through smoke, curtains, tall grass, tree folage (typically if there is absorption, there is obscuration).


  • Missile height (z-axis) is pretty much irrelevant over the distances involved. Assume level trajectories appropriate for human-sized shooter and target when determining the static information, and it will be "good enough". Small targets accounted for by a higher missile protection factor.
  • "Arching" (shooting at 45°+, my term?) is only available to bows (not crossbows), and only outdoors. Is much more difficult than line-of-sight fire, but avoids all intervening squares. Should be harder in denser woodlands, but that may not be worth the effort to represent.
  • Impossible shots can come off, that has always been a feature of RPGs, and differentiates them from purely physical models. Even if the stone wall is a level 100 obsticle, enough skill or luck can find a way around.

Not sure if anyone is still reading this thread, but I thought its better to get any ideas recorded for posterity ;)

Edited by trollson

Share this post


Link to post
Share on other sites

Are there any people who are working on this feature actually?

In RL, I'm working in geometrical modeling so maybe I can help cause I'm quite familiar with all these problems...

 

I've seen in the thread that ppl were talking about the Bresenham algorithm for finding the tiles crossed by an arrow but there's a little problem about this algorithm if you are willing to use it. This algorithm is used to draw digital lines which are only 0-connex (this means that pixels can be neighbour by their edges or by their vertices) so in this case some tiles will not be taken in account and it can maybe a problem.

I think that an algorithm that is able to draw 1-connex lines (pixels are neighbour only by their edges) will be more proper here. It's quite easy to make one from the Bresenham algorithm and also keep the big interest of this algorithm which is dealing only with integers. So if you need I can give you one I made some time ago (not before next week I think cause I'll be a little busy in RL).

 

I've also seen that you were also looking for a fast collision detection algorithm. I think the best way to do it (and the fastest) is to compute if the line cross the bounding boxes of the objects inside each tile you go with the line drawing algorithm. But it can be a problem for some objects (like trees) if you've got only 1 box per object. If it's the case, maybe it could be better to store several boxes per object, depending on the shape of the object (but they have to be given by human hand or the object have to be split in several little objects). Another solution can be also to store several spheres that cover the object because the intersection between a sphere and a line is very fast and faster than a box.

 

Well I don't know if you already had these ideas or not so I give them away in case of...

And if I can be of any help, I'll be glad cause I'd really love to see range weapons in EL :bow_arrow:

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×