targetting line

[luctius]

Hello all,

I'm creating a roguelike (as are we all I guess), which will have a lot of range combat.
Thing is, I'm trying to create a targeting line / projectile path, which seems pretty simple,
and I'm getting stuck creating one which matches the fov strategies.

The problem is, given a fov algorithm all the points in sight should be target-able. However
if I'm using Bresenham's algorithm, creating a line from a to b might fail due to obstacles,
but the line to c does go through point b.

Any suggestions on how to create such a targeting line.

For example:
The fov code finds B (anc C) from @, but my los does not.

Code: [Select]

@ . . . . . . . . .
 . . . ### B . . C

The reason I'm trying this approach is because I'm fiddling with different fov
strategies and not all of them provide an easy method of los. So my idea is
to give the fov code precedence in deciding if something is target-able, by
how do I extract  a nice projectile path out of it.

I have also looked at the digital lines strategy suggested at roguebasin,
but I do not have a good feeling how I should implement that. Any
suggestions on that would also be welcome.

Maybe I'm using a completely wrong approach here, but Im pretty stuck :S.

I am using plain old C, and am fiddling with both libfov and the digital fov
code used in kusumo.

Edit:
What I have now, is I use the los code of the digital fov, check which grid spaces
are touched, and then back-trace to get the targeting line suitable for that fov.
However, knowing that is can be seen, it seems like a lot of code to get the
targeting line...

[Eben]

Another option is to just have the projectile travel the Bresenham line and glide over objects (even walls in corners) to get to their target. It may look a bit silly, but it worked out fine in Attack the Geth and is obviously very easy to implement.

If you don't go that route, you'll either have to run your FOV with the same algorithm that you use for LOS, which will be fine for small areas but might get slow for large ones if you're running it for all creatures and such. Or you'll have to use something like Elias' algorithm which gives an anti-aliased line to the target, allowing it to "see" around edges.

You can see my FOV and LOS code here: https://github.com/SquidPony/SquidLib/tree/master/src/main/java/squidpony/squidgrid/fov My best results were from running shadowcasting for the the FOV and then Elias for the targeting line. Because of how Elias works, you have to check which end is which if you want to step through an arrow flight rather than just drawing a line.

[luctius]

Thank you very much, that is exactly what I am looking for.

Elias sounds promising. I found  Wu's line algorithm, but my google-fu
failed to find anything about Elias (except for your web page ).

Could you perhaps point me to some more documentation about Elias' Algorithm?

[Eben]

http://freespace.virgin.net/hugo.elias/graphics/x_wuline.htm

The main thing Elias did to the Wu algorithm is add better handling of 1-pixel length lines. The slight oddity he mentions at the endpoints in the page doesn't really matter since it makes sense mathematically that the end of the line is slightly anti-aliased (because it shouldn't reach past the center of the last pixel) and the amount it's off isn't significant.

[luctius]

Thank you very much. It works now.

I especially like your trick of using Elios' line as an intermediate.

Thanks again!