Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

HarryC

Line of fire in hex-based games

This topic is 5648 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m building a hex-based strategy game. I''ve got the basics of my engine down, and am now getting into the nitty-gritty details of things such of line of sight and line of fire. I can''t help but feel that I''m trying to re-invent the wheel when it comes to algorithms to figure this stuff out. Does anyone know of any links/books that address what I''m doing? As an example problem I''m working on: A character on hex location (45,16) wants to shoot an arrow at a character on hex (33,8). In between them could be hills, forests, etc. I first need to be able to determine which hexes would be entered by shooting the arrow from point A to B. This is non-trivial, and proving to be a pain-in-the-butt! I then need to determine what factors will affect the flight of the arrow and its overall chance of hitting the target -- this is a bit easier assuming I can figure out the first bit. Can anyone help?

Share this post


Link to post
Share on other sites
Advertisement
Hmmmm...

Just actually found a few articles on the subject that pretty much answer my question. In case anyone is interested:

http://www-cs-students.stanford.edu/~amitp/Articles/HexLOS.html
http://www-acaps.cs.mcgill.ca/~clump/Hex/HGAT.html


I''d still love to hear from others if they have further insights.

Cheers

Share this post


Link to post
Share on other sites
Glad to see someone else working on a hex based strategy game.
Im currently doing the same and am at the stage of of finishing my map editor. I would be interesested in seeing some screen shots. I have been using someelses (commercial game) graphics with my map editor, so I have to make my own graphics before I can show anything.

You must be from the UK

Cheers Scott

Share this post


Link to post
Share on other sites
Not from the UK, but I''ve spent over a year in Ireland, which seems to be about when I picked up the "cheers" phrase. :-)

Here''s a screen cap of my current terrain rendering engine:
http://www3.telus.net/public/colquho/currentscreencap.jpg

Certainly nothing fancy! I''m not going to bother with fancy graphics until such a time as I have a working game. All my character graphics are "borrowed" from around the web as well. :-)

Share this post


Link to post
Share on other sites
Actually it should be fairly trivial for a hex game. First have two pieces of information for each hex: 1. Max ''height'' of that hex. 2. Height of a unit on that hex. I assume you already have that since the arrow should go further if shot from the top of a mountain than if shot from the bottom of a ravine.

Now there are two ways to simulate the effect of shotting an array from point A to B:

One way would be a perfectly realistic kinematic simulation of projectile motion. This has alot of ups: You could easily change gravity and the game itself would change, weapon ''curves'' would be easily represented, it would be easy to simulate an upgraded weapon: The cannon ball might be shot out with an acceleration of 1000 meters/second instead of 700 meters/second. The major down side of this is that everything ''will'' be realistic. This isn''t always good for games. It might be cool, but it could easily ruin the fun in the game and its a pain in the butt developing reasonable heights for mountains as compared to valleys, etc..

The other way would to be to give each ranged weapon a ''projectile mobility''. Now on your map you would also give each hex a projectile mobility required to pass through it. For example: A mountain range might have a projectile mobility required of 3. A grass land might have a projectile mobility of 1. Now if I have a cannon that has a mobility of 5 that means I can shoot up to 5 grass lands away or 2 grass lands and a mountain away. This is reasonable and definitely adds strategy to the game. There is a major downside to this method. It doesn''t take into account where the projectile is coming from. I mean suppose you have a hill (2 mobility) that a cannon ball is coming into from a mountain (3 mobility). Since the cannon ball is coming from a significantly higher terrain it doesn''t make much sense for it to lose 2 mobility when passing through a lower terrain. This is where special rules would come into play. IE- After a projectile leaves a terrain, it gains a ''bonus'' equal to the mobility bonus of the current terrain minus the mobility bonus of the next terrain.

This means if an cannon was fired from a grass land ( 1 mobility ) into a mountain (3 mobility) it would cost 3 - (1 - 3) = 5 mobility. This is a very good thing, it perfects the simulation. If it was done the other way around and a cannon was shot from a mountain (3) onto a grass land(1) it would cost 1 - (3 - 1) = -1 mobility. Extremely logical. The weapon actually gains velocity while going from the high terrain to the lower terrain.

For further rules you can create a damage modifier based on how much mobility a weapon has left. For example, a cannon ball might start with 5 mobility and do a total of (remaining mobility*10/2+10) percent damage. So for example, shooting a cannon from a grass land onto a mountain would only do 10% damage ( 5 - ( 3 - (1 - 3)*10 + 10 )). Firing a cannon from that same mountain onto the grass land would do: ((5 - ( 1 - ( 3 - 1) ) )*20+10) 130% damage. This would make fighting well entrenched troops near impossible and make ignoring terrain suicidal.

This is a reasonable way to simulate it, and similiar to the way I had implemented combat in my RTS. Making terrain a huge part of games makes them so much more fun in my opinion. It really prevents the typical mentality of making 200 units and sending them off on auto attack while pumping out 200 more.

Share this post


Link to post
Share on other sites
I would love to be able to create a physics-based arc for a weapon, but I have a constraint that most game developers don''t have -- my game must be translatable into a set of easy-to-use table top rules. The last thing I want is for players of the table-top version of the game to pull out their scientific calculators to figure out bonuses/penaties for a projectile. :-)

The second suggestion you give is how I plan to implement this, though it is proving to be difficult figuring out the hexes to include in the calculation.

Share this post


Link to post
Share on other sites
quote:
Original post by InternetJunky
The second suggestion you give is how I plan to implement this, though it is proving to be difficult figuring out the hexes to include in the calculation.


Where exactly are you having the difficulties? Each time a person wants to fire a projectile from hex ''A'' to hex ''B'' you should predetermine the path. Now each calculation along this path should involve exactly 2 hexes. A ''coming from'' hex and a ''going to'' hex. There should be a series of calculations made between each of these two hexes. If all factors check out after the calculations are done (ie - the projectile is still alive and has sufficient mobility) then it moves on the next step in its path. Of course when its at its ''target'' hex the calculations phase would ''kill'' the projectile once it caused damage to the hex so it would never reach the next path step.

Share this post


Link to post
Share on other sites
quote:
Original post by haro
Where exactly are you having the difficulties? Each time a person wants to fire a projectile from hex ''A'' to hex ''B'' you should predetermine the path. Now each calculation along this path should involve exactly 2 hexes. A ''coming from'' hex and a ''going to'' hex. There should be a series of calculations made between each of these two hexes. If all factors check out after the calculations are done (ie - the projectile is still alive and has sufficient mobility) then it moves on the next step in its path. Of course when its at its ''target'' hex the calculations phase would ''kill'' the projectile once it caused damage to the hex so it would never reach the next path step.


Rather than try to explain this, I''ve taken a screen shot of the problem:
http://www3.telus.net/public/colquho/LOS_Problem.gif

Technically the hexes marked with an x are 7 hexes apart. However, if I were to include every hex that intersects a straight line between both hexes, I''d be intersecting with 9. The further the distance, the bigger the pain-in-the-butt!

So, what do I do? I can''t include every hex, and how do I make a generic set of rules to fairly determine the affect each intersecting hex has on line of sight? This is one of those problems that really gets compounded because I''m using hexes as opposed to square tiles.


Share this post


Link to post
Share on other sites
Interesting problem, I can see what''s wrong now! Do the board game and the computer games have to be identical? In the board game you can dumb down things a bit and simplify terrain bonuses like the old hex based pen and paper games. If you''re standing on a mountain you gain +2 range, +2 defense and +2 offense for example. Of course the mobility and offense bonuses don''t make much ''real life'' sense when you don''t have any elevation advantage over your opponent, but it makes things a hell of alot less tedious on the players.

For the computer game you could code a ''best results'' algorithm. If you know there are a minimum of 7 hexes that you have to go through to get from point A to point B then calculate every path from A to B that is 7 hexes and take the path that gives the best results (which would translate to the most mobility left in the previously offered system of attack). This is pretty typical algorithm problem and should be able to be brute forced with no performance worries.

The same algorithm could be used for unit movement and highlighting squares a unit can move to and pretty much of anything else. There is the slight downside that your projectiles may very well end up making somewhat erratic movements during flight, but the player doesn''t have to see the path that is actually chosen, if he wants to calculate the ''best'' path by hand let him feel free to see.. but when you fire the weapon it shouldn''t travel in hexes it should go from the attacker to the defender in a straight line.

Share this post


Link to post
Share on other sites
If you want it to work in both table top and coputer game, I think the best solution is to allow the table top player who shoot the projectile to choose the path they want among all the shortest path possible.
A rule could be that they cannot use more than 2 directions. Considering this hex:
```N
```_
NW/`\NE
SW\_/SE
```S
(edit: the ` are only there for filling!)

Valid paths would be along any 2 adjacent directions (N+NW, NW+SW, etc.). You could add a rule that you MUST go through "full hex" (a hex that is trivially on the line of sight).

For the computer version, use some kind of A* to find the best path for the projectile using (game_defined_weight_for_that_hex / (game_max_weight + 1) + 1) as the weight of each hex so the algorithm always use the shortest possible path and the most advantageous for the shooter.
To comply with the additional rule, you could pathfind in two passes, the first one finding trivial solutions ( from A to B with 27 hexes in between, the could be T1, T2 and T3 wich are trivial ) and the second pass would "relier les points" (link the trivial hex) effectively calculating multiple paths: A to T1, T1 to T2, T2 to T3 and T3 to B, using game weighting ( the 'projectile mobility' haro talked about )

Hope it helps, but I think I'm reinventing the wheel too! (although I think my own wheel could work)

oops! I began replying before haro's last post, so I couldn't consider what he said in his last post.

[edited by - vishnou00 on June 22, 2003 3:28:35 AM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!