Jump to content
XCOMUFO & Xenocide

Battlescape Assistance


dteviot

Recommended Posts

  • Looking for a texture I can use to the inside walls of a "human outpost". If you've seen the battlescape, then you probably realise that the way the terrain model works is the volume is carved up into cells, and the face of each cell is covered with a texture. So, I'm looking for a Government office standard puke beige or green wall.
  • Ideas on how we can efficiently do "line of sight" calculations on the battlefield.
    There are two line of sight issues.
    1. Figuring out which cells have been viewed by x-corp, so can be drawn.
    2. Figuring out which aliens are visible
      Only solution I have for 1 is give each cell a "has been seen" bit. Then each time a soldier moves a cell, calculate all the cells that are visible from the new position, and update the visible bit.
      Solution for 2 is similar, Set up an array of int32s, one for each cell. Then allocate a bit for each X-Corp soldier. Then, when a soldier moves, set the bits to indicate the cells they have a line of sight to. Then, to see if an alien is visible, we just check the bits in the int32 corresponding to the alien's location. The main problem with this is, as visibility range is a 90 degree cone, there's up to 8000 cells to check each time a soldier moves. And with 28 units, even if they only move one cell per second (I'm assuming we're going to have real time movement, as well as turn based) that's 240,000 cells to check, each second. That looks like it could get expensive.

    The visibility issue also brings me to the battlescape terrain. At moment, I'm not worrying about visibility, so I just construct the mesh at the start of the battlescape, and leave it at that. However, this is probably not going to work once we have "Fog of war", opening doors, desctructable terrain, etc. My thought for handling that is, we use the viewing fustrum to figure out what area of the battlescape is visible, and then construct on the fly the mesh for that area and a bit more. Then, when the viewing fustrum moves to reveal a different area of the battlescape, or the terrain changes, we recompute the mesh on the fly. This does mean that the camera angle may need some restrictions, so that we never try to view a patch that's bigger than, say 20 x 20 cells.

Link to comment
Share on other sites

I'll get your wall, what size would you like the texture? also I can split the textures up in the house if you want. so you can choose indiv tiles. that was we have grass, wall, stone etc etc Edited by Darkhomb
Link to comment
Share on other sites

I'll get your wall, what size would you like the texture? also I can split the textures up in the house if you want. so you can choose indiv tiles. that was we have grass, wall, stone etc etc

I figure texture sizes of 128 x 128.

Reason being, Shader 2 has max bitmap size of 2048 x 2048. That gives us 16 x 16 textures (or 256 textures total in a texture atlas.) I hope that's clear.

Yes, if you can find an assortment of ground and wall textures, that would be good.

Things we might want:

1. Human outpost walls/floor.

2. Alien outpost

3. Office building.

4. Outside (maybe.)

 

But I'm getting ahead of myself.

Link to comment
Share on other sites

There are two line of sight issues.
  1. Figuring out which cells have been viewed by x-corp, so can be drawn.
  2. Figuring out which aliens are visible
    Only solution I have for 1 is give each cell a "has been seen" bit. Then each time a soldier moves a cell, calculate all the cells that are visible from the new position, and update the visible bit.
    Solution for 2 is similar, Set up an array of int32s, one for each cell. Then allocate a bit for each X-Corp soldier. Then, when a soldier moves, set the bits to indicate the cells they have a line of sight to. Then, to see if an alien is visible, we just check the bits in the int32 corresponding to the alien's location. The main problem with this is, as visibility range is a 90 degree cone, there's up to 8000 cells to check each time a soldier moves. And with 28 units, even if they only move one cell per second (I'm assuming we're going to have real time movement, as well as turn based) that's 240,000 cells to check, each second. That looks like it could get expensive.

I think you're exaggerating on the visibility issue. 240,000 cells is enough for a 490x490 cell map to be fully visible, and I'm not sure if X-Com maps even reached 100x100 cells. In any case, X-Com units can see as far as 20 cells away, so we're looking at 400 cells per unit at perfect conditions, so 9,600 cells with 24 units. We also don't have to recheck any overlapping lines of sight, and as you calculate line of sight you can automatically figure out which cells and aliens are now visible. (and fog of war = explored squares - visible squares)
Link to comment
Share on other sites

There are two line of sight issues.
  1. Figuring out which cells have been viewed by x-corp, so can be drawn.
  2. Figuring out which aliens are visible
    Only solution I have for 1 is give each cell a "has been seen" bit. Then each time a soldier moves a cell, calculate all the cells that are visible from the new position, and update the visible bit.
    Solution for 2 is similar, Set up an array of int32s, one for each cell. Then allocate a bit for each X-Corp soldier. Then, when a soldier moves, set the bits to indicate the cells they have a line of sight to. Then, to see if an alien is visible, we just check the bits in the int32 corresponding to the alien's location. The main problem with this is, as visibility range is a 90 degree cone, there's up to 8000 cells to check each time a soldier moves. And with 28 units, even if they only move one cell per second (I'm assuming we're going to have real time movement, as well as turn based) that's 240,000 cells to check, each second. That looks like it could get expensive.

I think you're exaggerating on the visibility issue. 240,000 cells is enough for a 490x490 cell map to be fully visible, and I'm not sure if X-Com maps even reached 100x100 cells.

They did. Biggest was X-Com base, which was 120 x 120.

And the Xenocide battlescape limits are 128 x 128 x 8.

 

In any case, X-Com units can see as far as 20 cells away, so we're looking at 400 cells per unit at perfect conditions, so 9,600 cells with 24 units.

True, my calcs are slightly in error.

Assuming that visibility is 20 cells, and it's a 90% arc, then there's 314 cells, per level.

As there's up to 8 levels, thats 2513 cells per soldier, or 70,371 for 28 soldiers.

We also don't have to recheck any overlapping lines of sight, and as you calculate line of sight you can automatically figure out which cells and aliens are now visible. (and fog of war = explored squares - visible squares)

Can you tell me the algorithm to I avoid rechecking overlapping lines of sight? Note that while two soldiers may be viewing the same cell, their sight lines through it are different, and I need to plot the sight lines to trace to the next visible cells. (e.g. One soldier may be looking behind a tree from the left, the other from the right.

Link to comment
Share on other sites

There are two line of sight issues.
  1. Figuring out which cells have been viewed by x-corp, so can be drawn.
  2. Figuring out which aliens are visible
    Only solution I have for 1 is give each cell a "has been seen" bit. Then each time a soldier moves a cell, calculate all the cells that are visible from the new position, and update the visible bit.
    Solution for 2 is similar, Set up an array of int32s, one for each cell. Then allocate a bit for each X-Corp soldier. Then, when a soldier moves, set the bits to indicate the cells they have a line of sight to. Then, to see if an alien is visible, we just check the bits in the int32 corresponding to the alien's location. The main problem with this is, as visibility range is a 90 degree cone, there's up to 8000 cells to check each time a soldier moves. And with 28 units, even if they only move one cell per second (I'm assuming we're going to have real time movement, as well as turn based) that's 240,000 cells to check, each second. That looks like it could get expensive.

I think you're exaggerating on the visibility issue. 240,000 cells is enough for a 490x490 cell map to be fully visible, and I'm not sure if X-Com maps even reached 100x100 cells.

They did. Biggest was X-Com base, which was 120 x 120.

And the Xenocide battlescape limits are 128 x 128 x 8.

 

In any case, X-Com units can see as far as 20 cells away, so we're looking at 400 cells per unit at perfect conditions, so 9,600 cells with 24 units.

True, my calcs are slightly in error.

Assuming that visibility is 20 cells, and it's a 90% arc, then there's 314 cells, per level.

As there's up to 8 levels, thats 2513 cells per soldier, or 70,371 for 28 soldiers.

We also don't have to recheck any overlapping lines of sight, and as you calculate line of sight you can automatically figure out which cells and aliens are now visible. (and fog of war = explored squares - visible squares)

Can you tell me the algorithm to I avoid rechecking overlapping lines of sight? Note that while two soldiers may be viewing the same cell, their sight lines through it are different, and I need to plot the sight lines to trace to the next visible cells. (e.g. One soldier may be looking behind a tree from the left, the other from the right.

Well we still need to figure out the line of sight, but I'd assume we'd have some kind of "checked" flag so we don't have to recheck for the existance of anything in that particular tile and save a few time. After all, an alien will remain visible even if you look away after spotting it. (turn-based, anyways)

 

I was guiding myself by this article for the LOS info though I did forget about multiple levels. But I also found these articles on tile-based LOS calculation, if it helps:

http://www-cs-students.stanford.edu/~amitp...ineOfSight.html

http://sc.tri-bit.com/Computing_LOS_for_Large_Areas

Link to comment
Share on other sites

Correct me if I'm wrong, but if we go strictly turn based, you'll have a lot of time for a single calculation, since soldiers will be moved one at a time, and you only will have to check for line of sight as long as something is changing (moving).
Link to comment
Share on other sites

I was guiding myself by this article for the LOS info though I did forget about multiple levels. But I also found these articles on tile-based LOS calculation, if it helps:

http://www-cs-students.stanford.edu/~amitp...ineOfSight.html

http://sc.tri-bit.com/Computing_LOS_for_Large_Areas

Thanks SupSuper. I'll have a look at those.

 

Correct me if I'm wrong, but if we go strictly turn based, you'll have a lot of time for a single calculation, since soldiers will be moved one at a time, and you only will have to check for line of sight as long as something is changing (moving).

You're correct for turn based play. However, I plan on doing Apoc style Real time. That is, you give each combatant a set of orders, and they're all executed simultaneously.

Edited by dteviot
Link to comment
Share on other sites

  • 2 weeks later...

A very disorganized brain dump, comments and feedback greatly appreciated.

Looking at my list of tasks for the battlescape, I think I've sort of done the following:

  • Define the terrain model.
  • Build engine to render the terrain, and provide a UI to allow human to move camera to view terrain.
  • Put combatants on terrain, drawn at correct position, orientation and scale.

I'm now looking at:

  • Combatants move around the terrain, obeying the restrictions of the terrain. UI provided to allow setting rate time passes at. (Are we going real time or turn based?)

I've got the A* pathing engine working, and am now trying to think about how I get the alien combatants to actually move around the battlescape. My current thought is each alien combatant runs a simple state machine. And we have state machine for each tactic. E.g. "patrol", "attack", "bounding overwatch", "ambush", "panicked". So, step one would be implementing the "patrol" state machine.

The structure of this state machine is:

  1. Pick a waypoint
  2. Move to the waypoint.
  3. When waypoint reached, go to step 1.

The first problem I'm running into is how to pick the waypoint. (A* handles figuring out how to get from current position to waypoint.) So, any ideas? At the moment, the best I can think of is: "Head towards "centre of mass" of enemy forces."

Additional comments:

  • What other state machines (tactics) are there?
  • What are the states making up each of these machines?
  • What are all the events that could occur on the battlescape that might trigger a change of state? (Well, this one's kind of covered by the previous.) However a quick list that comes to mind are:
    • Enemy sighted by this combatant
    • Enemy sighted by allied combatant.
    • This combatant is being attacked.
    • This combatant has been injured.
    • Allied combatant is being attacked.
    • Allied combatant has been killed.
    • Enemy combatant has been killed.
    • Allied combatant has been knocked unconscious.
    • Enemy combatant has been knocked unconscious.
    • Enemy combatant has recovered consciousness.
    • Allied combatant has recovered consciousness.
    • This combatant has recovered consciousness.
    • This combatant is in weapon range of enemy.
    • Enemy is in weapon range of this combatant.
    • This combatant's weapon is out of ammo.
    • This combatant is out of ammo.
    • Waypoint reached.

    [*]How I think controlling the combatants will work?

    • Currently still very vague. Each combatant has an "orders queue". Orders are very simple things like:
      Move to position X, Move item X in inventory from position Y to Z, Do action X, with object Y, in hand Z. (Shooting weapons falls into this class.)
    • Each combatant has a "controller". The controller puts orders into the combatant's event queue. The combatant signals the controller when events happen. (e.g. the list above.) For aliens, the controller is the state machine I mentioned previously. For
      combatants under player's control, the controller is probably a thin wrapper around the order queue, and GUI.
    • Ideally, we can "plug" a controller in an out, so when aliens mind control an X-Corp unit, the "panic" state machine is plugged in. When Player mind controls an alien, the "player controller" is plugged in.

Thought is actions are attached to items, so look at item to get list of actions it supports. The actions and information needed to perform them are:

  • Throw
    • intended destination

    [*] Shoot

    • target

    [*]Prime (a grenade)

    • Time before detonation

    [*]Prime (Prox Grenade)

    • Does the prox grenade have a detection range setting?

    [*]Guide (give a missile a waypoint)

    • Co-ordinates of waypoint

    [*]Hit

    • target

    [*]Heal (use med kit)

    • target

    [*]Scan (using Motion sensor)


    [*]Psi Probe

    • target

    [*]Panic Attack

    • target

    [*]Mind Control

    • target

Other notes

  • So far as I can see, there's no difference between "hit" and "shoot".
  • There are 3 types of shot (auto, snap and aimed), however, they only differ in the properties of the action itself, they don't need to be passed in as parameters.
  • It is assumed that the item performing the action, the combatant using the item, and the item's location on battlescape are passed to the action, along with the action specific information.
  • What does the Action class hierarchy look like?
    • void DoAction(params). // Actually does the action
    • errorcode CanDo(params). // returns true if action can be performed.
    • Some way of telling caller the additional parameters the action needs, and how to obtain them. (Possibly its just going to be an enumeration?)

Other orders:

  • Kneel?
  • Stand? Is that implied by move?
  • Move to. (Later, this may include speed. E.g. Walk, Run, Crawl.)
  • Turn (to face direction X)
  • Select group of combatants (to give all same order to at once)?

What have I missed?

 

Things that I think I need to do sometime soon:

  • Define the UI for the battlescape. How actions are done, etc
  • Add HasLineOfFire(pos x, pos y) to terrain, Checks if there's clear line from x to y on the battlescape. (Note, probably need to have different rule for grenades.)
  • Finish parsing combatant.xml, so that can create alien forces at start of battlescape, using information from combatant.xml.
  • Parse actions from item.xml.
  • May want to update current terrain render engine to use int32 for indexes, instead of int16?
  • Update terrain render engine, only build mesh for part of terrain that is visible on screen.
  • Want way of building battlescape terrains of reasonable size (e.g. 128 x 128). StaffSargeant is working on this, but I'm not sure when he will have any results. If nothing in next week, may need to build something simple myself. Something like the UFO: Aftermath city missions. (In anticipation: where to find screen shots? How big were those maps, in movement units, on average? How wide were the buildings?)
  • Look at UFO:AI code, see what it's AI code looks like? Maybe Google for game AI, bot, state machine? Could we steal AI ideas from other games?
  • For movement, need to at least give combatants the attributes for "TUs per turn" and "TUs remaining this turn". However, as combat isn't far off probably pay to add "Max Health points", "Wound damage", "Stun Damage".
  • Also, there's attributes that soldiers have that aliens never will "Missions", "Kills", "Date hired" (recording date hired, and then calculating "Days employed" when requested is probably easier than tracking "Days employed".)

Link to comment
Share on other sites

Link to comment
Share on other sites

A very disorganized brain dump, comments and feedback greatly appreciated.

Looking at my list of tasks for the battlescape, I think I've sort of done the following:

  • Define the terrain model.
  • Build engine to render the terrain, and provide a UI to allow human to move camera to view terrain.
  • Put combatants on terrain, drawn at correct position, orientation and scale.

I'm now looking at:

  • Combatants move around the terrain, obeying the restrictions of the terrain. UI provided to allow setting rate time passes at. (Are we going real time or turn based?)

I've got the A* pathing engine working, and am now trying to think about how I get the alien combatants to actually move around the battlescape. My current thought is each alien combatant runs a simple state machine. And we have state machine for each tactic. E.g. "patrol", "attack", "bounding overwatch", "ambush", "panicked". So, step one would be implementing the "patrol" state machine.

The structure of this state machine is:

  1. Pick a waypoint
  2. Move to the waypoint.
  3. When waypoint reached, go to step 1.

The first problem I'm running into is how to pick the waypoint. (A* handles figuring out how to get from current position to waypoint.) So, any ideas? At the moment, the best I can think of is: "Head towards "centre of mass" of enemy forces."

Additional comments:

  • What other state machines (tactics) are there?
  • What are the states making up each of these machines?
  • What are all the events that could occur on the battlescape that might trigger a change of state? (Well, this one's kind of covered by the previous.) However a quick list that comes to mind are:
    • Enemy sighted by this combatant
    • Enemy sighted by allied combatant.
    • This combatant is being attacked.
    • This combatant has been injured.
    • Allied combatant is being attacked.
    • Allied combatant has been killed.
    • Enemy combatant has been killed.
    • Allied combatant has been knocked unconscious.
    • Enemy combatant has been knocked unconscious.
    • Enemy combatant has recovered consciousness.
    • Allied combatant has recovered consciousness.
    • This combatant has recovered consciousness.
    • This combatant is in weapon range of enemy.
    • Enemy is in weapon range of this combatant.
    • This combatant's weapon is out of ammo.
    • This combatant is out of ammo.
    • Waypoint reached.

    [*]How I think controlling the combatants will work?

    • Currently still very vague. Each combatant has an "orders queue". Orders are very simple things like:
      Move to position X, Move item X in inventory from position Y to Z, Do action X, with object Y, in hand Z. (Shooting weapons falls into this class.)
    • Each combatant has a "controller". The controller puts orders into the combatant's event queue. The combatant signals the controller when events happen. (e.g. the list above.) For aliens, the controller is the state machine I mentioned previously. For
      combatants under player's control, the controller is probably a thin wrapper around the order queue, and GUI.
    • Ideally, we can "plug" a controller in an out, so when aliens mind control an X-Corp unit, the "panic" state machine is plugged in. When Player mind controls an alien, the "player controller" is plugged in.

Thought is actions are attached to items, so look at item to get list of actions it supports. The actions and information needed to perform them are:

  • Throw
    • intended destination

    [*] Shoot

    • target

    [*]Prime (a grenade)

    • Time before detonation

    [*]Prime (Prox Grenade)

    • Does the prox grenade have a detection range setting?

    [*]Guide (give a missile a waypoint)

    • Co-ordinates of waypoint

    [*]Hit

    • target

    [*]Heal (use med kit)

    • target

    [*]Scan (using Motion sensor)


    [*]Psi Probe

    • target

    [*]Panic Attack

    • target

    [*]Mind Control

    • target

Other notes

  • So far as I can see, there's no difference between "hit" and "shoot".
  • There are 3 types of shot (auto, snap and aimed), however, they only differ in the properties of the action itself, they don't need to be passed in as parameters.
  • It is assumed that the item performing the action, the combatant using the item, and the item's location on battlescape are passed to the action, along with the action specific information.
  • What does the Action class hierarchy look like?
    • void DoAction(params). // Actually does the action
    • errorcode CanDo(params). // returns true if action can be performed.
    • Some way of telling caller the additional parameters the action needs, and how to obtain them. (Possibly its just going to be an enumeration?)

Other orders:

  • Kneel?
  • Stand? Is that implied by move?
  • Move to. (Later, this may include speed. E.g. Walk, Run, Crawl.)
  • Turn (to face direction X)
  • Select group of combatants (to give all same order to at once)?

What have I missed?

 

Things that I think I need to do sometime soon:

  • Define the UI for the battlescape. How actions are done, etc
  • Add HasLineOfFire(pos x, pos y) to terrain, Checks if there's clear line from x to y on the battlescape. (Note, probably need to have different rule for grenades.)
  • Finish parsing combatant.xml, so that can create alien forces at start of battlescape, using information from combatant.xml.
  • Parse actions from item.xml.
  • May want to update current terrain render engine to use int32 for indexes, instead of int16?
  • Update terrain render engine, only build mesh for part of terrain that is visible on screen.
  • Want way of building battlescape terrains of reasonable size (e.g. 128 x 128). StaffSargeant is working on this, but I'm not sure when he will have any results. If nothing in next week, may need to build something simple myself. Something like the UFO: Aftermath city missions. (In anticipation: where to find screen shots? How big were those maps, in movement units, on average? How wide were the buildings?)
  • Look at UFO:AI code, see what it's AI code looks like? Maybe Google for game AI, bot, state machine? Could we steal AI ideas from other games?
  • For movement, need to at least give combatants the attributes for "TUs per turn" and "TUs remaining this turn". However, as combat isn't far off probably pay to add "Max Health points", "Wound damage", "Stun Damage".
  • Also, there's attributes that soldiers have that aliens never will "Missions", "Kills", "Date hired" (recording date hired, and then calculating "Days employed" when requested is probably easier than tracking "Days employed".)

The Proximity grenade has a 1 tile sensing radius, that is to say if you step on any one of the 8 tiles surrounding the proximity grenade, it explodes. The proxy doesn't sense vertical movement though, so if a unit flys over it nothing happens.

 

Just to clarify, the Motion scanner only picks up units which moved during the round and within 10 tiles of the scanner. Units beyond the limit remain invisible on the scanner.

 

As for the waypoints, we could use the center of mass approach as that closely models how aliens move in the original game. The only difference was that in the original game, each terrain "block" (a block is either a 10x10 or 20x20 matrix of tiles) had certain tiles defined as waypoints. The aliens would follow the waypoints and if they didn't spot a unit, continued on to the next one until they did.

 

"Hit" is supposed to be an action for using a weapon without ammo. Basically like a baseball bat to crack over the skull of a nearby alien. It doesn't do much damage (and we haven't defined damage yet for the objects in the game) but it allows you to kill without ammo just in case you run out. This feature was supposed to be in the original game but was dropped for some reason.

 

Other orders: don't forget the ability to open doors without walking through them and also flying/changing levels via elevators or lifts.

 

Sorry, this is all the time I have today. Hopefully some of this is helpful. ;)

 

- Zombie

Link to comment
Share on other sites

  • 2 weeks later...

About finding visible aliens:

 

Set up an array of int32s, one for each cell. Then allocate a bit for each X-Corp soldier. Then, when a soldier moves, set the bits to indicate the cells they have a line of sight to. Then, to see if an alien is visible, we just check the bits in the int32 corresponding to the alien's location. The main problem with this is, as visibility range is a 90 degree cone, there's up to 8000 cells to check each time a soldier moves. And with 28 units, even if they only move one cell per second (I'm assuming we're going to have real time movement, as well as turn based) that's 240,000 cells to check, each second. That looks like it could get expensive.

 

Why not have each soldier check if it can see each alien, roughly a maximum of 28 soldiers x 30? aliens = 840 checks. Though I would assume you would need to have the aliens do the same for the soldiers so 840 x 2 = 1680 checks. Civies would raise the number higher still though I'm not sure if we are going to have Civies react to seeing aliens and/or soldiers.

 

I'm not really sure how the viewing frustrum is calculated / generated for the fog of war. 2 ways I'm thinking:

  1. A function that will return the set of cells viewable from a given location and viewing angle
  2. A function that checks if a cell is visible from a given location, and iterate through all possible cells (after some culling)

If it is the first way then isn't checking if the Alien's Position is in the set rather cheap? Otherwise we would need a sorting/indexing of it so we can avoid looping through all cells. Not sure how difficult a hashing of the set would be.

 

The second way would be by far the easiest, simply check each of the aliens' cells is visible from each of the soldiers and presto.

 

As I've thought of this more, what about ray tracing from each soldier to each alien? Would need to remove any aliens outside of the viewing range of the given soldier, and any lines not in the viewing angle of the soldier.

 

Not sure if this was much help, but obviously checking or updating every cell is going to be expensive so a better solution would involve just iterating through the aliens.

Link to comment
Share on other sites

About finding visible aliens:

 

Set up an array of int32s, one for each cell. Then allocate a bit for each X-Corp soldier. Then, when a soldier moves, set the bits to indicate the cells they have a line of sight to. Then, to see if an alien is visible, we just check the bits in the int32 corresponding to the alien's location. The main problem with this is, as visibility range is a 90 degree cone, there's up to 8000 cells to check each time a soldier moves. And with 28 units, even if they only move one cell per second (I'm assuming we're going to have real time movement, as well as turn based) that's 240,000 cells to check, each second. That looks like it could get expensive.

 

Why not have each soldier check if it can see each alien, roughly a maximum of 28 soldiers x 30? aliens = 840 checks. Though I would assume you would need to have the aliens do the same for the soldiers so 840 x 2 = 1680 checks. Civies would raise the number higher still though I'm not sure if we are going to have Civies react to seeing aliens and/or soldiers.

 

I'm not really sure how the viewing frustrum is calculated / generated for the fog of war. 2 ways I'm thinking:

  1. A function that will return the set of cells viewable from a given location and viewing angle
  2. A function that checks if a cell is visible from a given location, and iterate through all possible cells (after some culling)

If it is the first way then isn't checking if the Alien's Position is in the set rather cheap? Otherwise we would need a sorting/indexing of it so we can avoid looping through all cells. Not sure how difficult a hashing of the set would be.

 

The second way would be by far the easiest, simply check each of the aliens' cells is visible from each of the soldiers and presto.

 

As I've thought of this more, what about ray tracing from each soldier to each alien? Would need to remove any aliens outside of the viewing range of the given soldier, and any lines not in the viewing angle of the soldier.

 

Not sure if this was much help, but obviously checking or updating every cell is going to be expensive so a better solution would involve just iterating through the aliens.

I have to check all 8000 cells in the soldier's vision for cells that were not previously seen. (The fog of war, where X-Corp player can't see any cells that have not been seen by an X-Corp soldier.)

That said, I can defer fog of war on cells for the moment, and just use line of sight on enemy forces initially.

 

Anticipation for the future/thoughts/observations/request for help:

  • Need to add a model element to battlescape items in item.xml, so know what to draw on battlescape when item is shown. (Dropped, in hand, thrown, etc.)
  • Model element in xml files needs a scale element. The problem we currently have is all models are scaled to fit inside a sphere of radius 1. Unfortunately, because the Morlock and Viper have disproportionately long arms, this means that on the battlescape they"re scaled to be a lot shorter than humans. And of course, this scaling simply doesn"t work for items being held.
  • Sound on the battlescape. Add a sound attribute to each action in item.xml. It is played when the action starts. Question: do some actions need multiple sounds? E.g. "miss", Grenades, probably don"t have an arm sound, but do have an explode. Should Blaster Bomb launcher have a "set waypoint" as well as "fire"? (In order to keep things simple, perhaps don"t have a "miss" sound, as you can tell a hit from the enemy"s scream of pain. And have a generic "explosion" sound that"s used by missiles, grenades, etc.)
  • Anyone want to make up a list of sounds? And what"s a minimal set we can get away with? (e.g. we have as single "fire" sound for all weapons. We can replace it with weapon specific sounds as they become available.)
  • Also for each combatant have a set of sound elements that are played when certain events occur. E.g.
    • Moving,
    • Hit by enemy fire
    • Die
    • See enemy that wasn"t seen previously

    What other sounds will we need?

    Some sounds might have multiple versions. (e.g. Cyberdisk might have multiple hit screams, just to be less repetitive.)

    [*]Visibility calculations. As I"ve said before, having a matrix that indicates which cells are under observation can make alien AI easier. E.g. sneak up on X-Corp soldiers, find good sniping positions. Etc. Efficiently calculating the matrix is hard. But I had the following thoughts.

    • Perfection isn"t required. We just need something that"s "close enough".
    • Simple rule for line of sight. Is a line from centre of start cell to centre of end cell blocked by a wall, floor or contents of a cell?
    • If we do this for every cell in sight range, then this is an O(n^3) operation, where n is sight range. There will be O(n^2) cells, and to trace the ray will need to examine on average O(n) cells.
    • So for first cut, just use this method. Optimise later if needed.
    • Possible Optimisations.
      • We don"t need to trace a ray to every cell, just the cells on the outer edge of the site range. As we head to the outer edge, we will be examining the cells inside the range, and can mark their visibility as we pass through. This should drop work to O(n^2).
      • Second, assume we have a soldier at (0,0) and we trace out the ray to (20,0). The next ray we want to trace out is going to (0,0), and we trace out the ray to (20,1). Note that for the first half of the ray"s length, it"s going to be going through the same cells as the previous ray. So, if we could avoid the multiple testing of cells, this is might also speed things up.
        The idea is, for each cell on a ray, Cell(n), we can compute the adjacent cell the sight line entered from Cell(n-1). Then, visibility of Cell(n) = visibility of Cell(n-1) and visibility of cell(n) from cell(n-1). So, we can precompute a table that says for each Cell(n), the Cell(n-1) that we need to compute first. Next step is reverse the table and get a new table that says, if Cell(n) is visible, then this is the list of adjoining cells that can be checked for visibility.
        Other ways of doing this might also be possible. I realised that this won't work

Edited by dteviot
Link to comment
Share on other sites

×
×
  • Create New...