Battlescape Inventory

[[dteviot]]

Some thoughts. As always, feedback is appreciated.

 

There are three reasons for keeping track of the "dropped" items on the battlescape

1. Combatants are able to pick up the item when they're in the same terrain cell.
   
2. Drawing the item on the battlescape
   
3. Knowing if a combatant is beside a proximity mine.
   

Now, in UFO2000, the way items are tracked is each battlescape cell has an item pointer. If there's an item in the cell, then the pointer points to the item. Otherwise it's null. This system works well for point 1, and also for point 2. Because in UFO2000, the render has to walk every cell in the viewing fustrum, to render the walls, floor and combatant, so adding an item pointer works well.

 

For XNA, a pointer in each cell isn't quite so desirable. Mostly because we DON'T walk all the cells (in the fustrum) to render the scene. (There are potentially 20 x 20 x 8 = 3,200 cells in the fustrum)

 

So, I suggest the following design.

1. We maintain a list of all the loose items.
   
2. We walk the list, drawing the items that are in the fustrum. (In most cases, there's not going to be a lot of items on the battlescape.)
   
3. If performance is an issue, we can keep an index to the items, sorted by X, Z, Y co-ordinate. And use that to reduce the list of items to examine. (Find north west corner of viewing fustrum, then look up first item in index that has that location or higher, then take each item in order until item's location is past the south east corner of the fustrum.
   
4. Also, when there are multiple items in a cell, we only draw the biggest item. (Which we can determine from the "backpack space" used.
   

 

This structure is optimized for rendering (which occurs 60 time/second).

It's not very efficient for checking if combatant can pick up an item. But that's doesn't require high performance. As it only needs to be done when player opens the equipment screen.

As regards testing for prox mine. I suggest we add a bit to each terrain cell, "in prox mine sensor range". Then when a combatant moves into a cell, it's just a fast lookup to see if a prox mine is set of, in which case we can do the expensive search for the mine that's been detonated.

 

Aside, at current time, combatants are drawn on screen by walking the list of all combatants and drawing them.

Should I look at providing an index to do similar culling? (Answer: No, not until it proves necessary.)

 

Other "dynamic" information to track for each terrain cell on battlescape

• if cell contains a combatant.
  
• has cell been observed by an X-Corp combatant.
  
• is cell being observed by X-Corp combatant(s) (Needed for reactions) (May also be useful for alien AI to pick good shooting position)
  
• is cell being observed by Alien combatant(s) (Needed for reactions)
  
• Number of turns since smoke/fog was in cell (for tracking smoke/fog disipation)
  
• Number of turns cell has been on fire for. (for tracking fires going out.)
  
• Is cell lit? (Not sure about this one.)
  

 

Note, it could be argued that if we don't put items in cells, we shouldn't put combatants either.

The counter argument is that combatants block travel in a cell, so if the cell isn't tagged, then the pathfinder needs to look up if cell is occupied.

That said, at current time, I'm storing an index to combatant in each terrain cell. This could be reduced to a single bit, if space becomes critical.

Edited February 12, 2008 by dteviot

[[Mad]]

As regards testing for prox mine. I suggest we add a bit to each terrain cell, "in prox mine sensor range". Then when a combatant moves into a cell, it's just a fast lookup to see if a prox mine is set of, in which case we can do the expensive search for the mine that's been detonated.

I guess it could save some calculations to not check every cell every time, but only check for the "in prox mine sensor range"-bit if and when a proximity mine has been armed and not yet exploaded.

[[dteviot]]

As regards testing for prox mine. I suggest we add a bit to each terrain cell, "in prox mine sensor range". Then when a combatant moves into a cell, it's just a fast lookup to see if a prox mine is set of, in which case we can do the expensive search for the mine that's been detonated.

I guess it could save some calculations to not check every cell every time, but only check for the "in prox mine sensor range"-bit if and when a proximity mine has been armed and not yet exploaded.

Well, when a combatant moves from one cell to another, we need to to check visibility anyway (to see if combatant has moved into/out of view of the opposing forces. So checking the proximity mine bit at the same time is probably the same amount of work as 1. checking if there are any prox mines, then 2. is this cell in detection range of a prox mine. So least work is just check the bit.

[Pi Masta]

As regards testing for prox mine. I suggest we add a bit to each terrain cell, "in prox mine sensor range". Then when a combatant moves into a cell, it's just a fast lookup to see if a prox mine is set of, in which case we can do the expensive search for the mine that's been detonated.

 

Why not have a pointer/index to the actual prox mine? Use NULL if there isn't one, bypassing the search entirely. I don't remember if the original allowed multiple prox mines to overlap triggering areas (or if the first to explode would just destroy the other mine), but if we allow it we would either need a list of pointers or use your method above.

 

Also what about the type of tile in the cell, for when destroying walls or floors etc, or is that handled by a different system?

 

I've been out of the loop for some time now, glad to see you all are making progress. I may or may not be able to get back to helping out in the future.

 

Good Luck and Cheers!

[[dteviot]]

As regards testing for prox mine. I suggest we add a bit to each terrain cell, "in prox mine sensor range". Then when a combatant moves into a cell, it's just a fast lookup to see if a prox mine is set of, in which case we can do the expensive search for the mine that's been detonated.

 

Why not have a pointer/index to the actual prox mine? Use NULL if there isn't one, bypassing the search entirely. I don't remember if the original allowed multiple prox mines to overlap triggering areas (or if the first to explode would just destroy the other mine), but if we allow it we would either need a list of pointers or use your method above.

The reason for just a single bit flag per cell is because the battlescape has 129,032 (127 x 127 x 8) cells. So if we allowed a prox mine pointer per cell, that"s 500,000 to 1 Mbyte of storage needed. If we make it a bit flag, then it"s only 129,032 bytes, and we have 7 bits spare we can use. If we allow smoke and fire to last for up to 8 turns, then we need 3 bits each to hold the burn time, and we can use the remaining bit to hold the "has been seen" bit. Now, I know someone is going to say, "But computers have hundreds of megabytes, what do we care about a meg or two?" There are two responses to this.

• If you use a meg here and another couple of megs there, it soon adds up to lots of megs, and that IS an issue. Once paging starts, performance goes into the toilet.
  
• While PCs have hundreds of megs of RAM, typically they only have a few megs of cache. So keeping size down still helps, as the PC can keep more in cache, and cache is typically 10 times faster than main memory.
  

Also what about the type of tile in the cell, for when destroying walls or floors etc, or is that handled by a different system?

Yes, a different system.

[Pi Masta]

The reason for just a single bit flag per cell is because the battlescape has 129,032 (127 x 127 x 8) cells. So if we allowed a prox mine pointer per cell, that"s 500,000 to 1 Mbyte of storage needed. If we make it a bit flag, then it"s only 129,032 bytes, and we have 7 bits spare we can use...

 

I understand completely, wasn't quite sure about the size of maps we were planning on using. I got several suggestions/ideas to bounce off to you all.

 

Prox Mines

Don't know why it didn't occur to me until now, but how about iteraterating through a list of armed prox mines and calculate a list of trigger cells? Either do this every time a combantant moves into a cell or more likely use a caching system updating whenever an armed prox is thrown/dropped and explodes/destroyed. Might need to store it as a mapping instead of a list so that we know which prox mine is triggered by which cell (keys would be the cell positions, data would be pointer or index to mine).

 

Fire and Smoke

I believe we could use a similar system for the fire and smoke cells. Store the cell positions as keys in a mapping and the data would be the time remaining to burn/smoke. Could even add more data like thickness of smoke and maybe intensity of the fire for damage and spreading. If we store them in each cell we have to check all 129,032 cells and decrement the flags every turn/second, vs just the number of cells affected. Might need to keep a single bit indicating if fire and/or smoke is present for the pathfinding and AI. Kind of depends on how expensive checking if a key is present in a mapping.

 

Cell Lighting

We probably do need to store how if a cell is lit and possibly a lighting level (maybe 2 or 3 bits). For the line of sight we need to be able to see farther in the night if the cell is lit. A lighting level would make for more realistic lighting. Of course during the day all of this would be ignored, or we could set all the cells to fully lit on start up.

 

Cell Visibile to Aliens

On another note: would the tracking of "Is cell visible to Aliens for reactions" be necessary if we use the ray tracing method I posted recently in the other thread? I understand the need for a "Is visible by XCORP" for helping the AI (help it cheat anyways )

 

That said, we might want to keep it for future possibilities (aka post v1):

• if we decide to allow the player to be the aliens against an AI XCORP,
  
• we allow the AI to take over for the player completely for an "autocombat" system
  
• In Real Time the AI for soldiers won't run out in the open on their own
  

Lastly it may be useful for the AI controlling Civilians. They are going to be at least semi intelligent and run for cover right?

 

Path Blocking

Maybe the "Is Combantant in Cell" should be revised to "Is Cell Blocked" and can be flaged by the terrain, the path finder shouldn't care why a cell is blocked. Semantics I know, but if we can use it for a more general case why not?

 

My

[Zombie]

BTW, the way Enemy Unknown handles this stuff is data files. See the Battlescape Files section in the X-COM wiki for more info. Separate data files are a lot smaller than a global map file with everything listed as the separate file is only as big as the number of objects, combatants, etc. (Technically in EU most of the data files are static in size but unused records in a file are just nulled out). Don't know if this is something to consider here, but using a data file is a good way to cut down on the number of pages performed.

 

- Zombie

Edited March 15, 2008 by Zombie
URL fix

[red knight]

Having cells information is important. However, as noted by some here, for dynamic objects you have to handle it with the inverse relationship because it is a waste or resources and the search problem becomes unwildly. What you have to do is the following:

 

- Have a tracking entity that can match unique objects with the current cell (you can even agregate that into the entity)

- Implement a typed/untyped intersection query for that. Lets say

public IList<Entity> FindEntities ( Where, Type type );
public IList<Entity> FindEntities ( Where );
public IList<Entity> FindEntities<T> ( Where )
{
return FindEntities ( Where, typeof(T) );
};

- All entities should have a Entity.CurrentCell to be able to do the match with the cell data.

 

On the other side, there is value in having loose grids too for the "Cell Data" too; but that is too complex for now.

 

Greetings

Red Knight

[red knight]

BTW you can go a little overboard with this and use the Where as a Lambda condition in C# 3.0 (Visual Studio 2008) or in preparation as a delegate in C# 2.0. That helps a lot for intersection queries. An example of that can be found here: http://blogs.msdn.com/lukeh/archive/2007/0...r-in-c-3-0.aspx

 

Greetings

Red Knight