Jump to content
XCOMUFO & Xenocide

2x2 Units


dteviot

Recommended Posts

 

Well, the first problem is that the current path finding uses a 1x1, and won't directly work for 2x2.

That said, there's several ways of getting 2x2 to work. The simplest is just use the existing algorithm, but when build a list of the reachable adjacent neighbors of a cell, check that all four cells the unit cover can move in that direction. (Note, it's a bit more tricky than that. Consider the case of wanting to move one cell north, and the two cells north of the unit have no south walls, but there's a east/west wall between the cells.)

Other methods are:

  • Compute a terrain for the 2x2 units using sampling cells in a 2x2 pattern from the existing map.
  • Use a 2D version of the Quake3 AAS. (In simple terms, use a 2D BSP tree to divide each level of the map into a set of convex polygons (with walls only on the edges of each polygon) and note where combatants can move between polygons.
    It's a lot more work, but will aid tactical reasoning. e.g. any polygon that has only two adjacent polygons is a potential chokepoint.

 

However, other potential issues with 2x2 units are:

  • Stairs/Ramps
  • Centering units. Currently 1x1 combatants only exist right at the center of the current cell they're in. (OK, while moving they're not, but the logic moves combatants from center to center in an uninterupted task. i.e. Shooting, pathfinding, etc only happen when a combatant has finished the move from one cell to another.
  • A 2x2 unit ISN'T centered in a cell. (The center is at the corner of 4 tiles.) This has issues for distance, line of sight, line of fire, heading to target, etc.

Link to comment
Share on other sites

The UFO:EU system worked with 2x2 units but had some glitches. For example, you could mind control a part of the 2x2 unit. 1/4, 2/4 or 3/4. Then during the alien round, the other part would attack the part you mind controlled :S. I think we can safely assume that the original developers though the 2x2 units as 4 1x1 ones. Edited by kafros
Link to comment
Share on other sites

The UFO:EU system worked with 2x2 units but had some glitches. For example, you could mind control a part of the 2x2 unit. 1/4, 2/4 or 3/4. Then during the alien round, the other part would attack the part you mind controlled :S. I think we can safely assume that the original developers though the 2x2 units as 4 1x1 ones.

 

I just had an idea which I'll try to draw: The map is a grid of 1x1 tiles. Instead of forcing the 2x2 units to work on that 1x1 grid, they could work on a 2x2 grid. So they would be like a "large 1x1" unit on a "grid with larger 1x1 tiles".

 

Have a look at the picture (I couldn't make it much better, so I'll be happy to elaborate on it if needed)

I'm sorry, but I don't quite follow. How does this differ from "Compute a terrain for the 2x2 units using sampling cells in a 2x2 pattern from the existing map."

That is, take the existing 1x1 map. Then produce a new map where every cell in the map is made by taking a 2x2 group of cells from the original 1x1 map.

e.g., to produce the cell at (0,0) on the new map, we examine the cells (0,0), (0,1), (1,0) and (1,1) on the original map.

Memory required to store the new map not be an issue, as the new map will be 0.25 the size of the original.

However, it does have a few issues.

  • the 2x2 units must move in multiples of 2 cells (they can't just move one cell)
  • Stairs and ramps are still a problem, due to the compression of the map. (A stair is composed of 4 tiles adjacent tiles, one at hight 0, one at height 0.3, one at 0.6 and one at the next level.) Sampling makes stair detection difficult.

Edited by dteviot
Link to comment
Share on other sites

As I said before, my preference would be something that chunks up the map into convex polygons, and marks any polygons that 2x2 units can't use.

e.g. the map you supplied can be chunked up into 5 polygons (as shown below), only the 1x1 area can't be used by a 2x2 unit. Note, inside each polygon, path finding is easy, as there are no obstacles inside a single polygon. Also the number of polys is much smaller than the number of cells, resulting in faster path finding.

2x2.03.PNG

Link to comment
Share on other sites

If the current pathfinding is relatively cheap, then I would think it preferable to build another copy of the path grid, adjusted for 2x2 units (take every cell as the NW quarter's position, mark as impassable if there's a >0.4 height difference or an internal wall in it, mark height as the mean of the involved 4 heights, apply passability from the already-generated four affected 1x1 cells; worst case scenario is a fully open terrain, when it takes 4-8 times as long to generate, but the same time to find the optimal path). Chunking is good if the map itself is accomodated for it, but consider the first attached corner: a 2x2 unit should fit through, using an auxiliary 1x1 chunk which would be marked impassable to begin with. If we disallow that, there's still the issue of width 2 passages (second image): chunking out (2+)x(2+) pieces has to leave single 1x1 cells which have to be used during pathfinding. These issues can't really be evaded by map design if the terrain is destructible.

2x2path1.PNG

2x2path2.PNG

Edited by centurion
Link to comment
Share on other sites

  • The second image you give, all the cells from a convex polygon. (Every cell has a line of sight on every other.)
    Therefore, the entire area should be represented as a single polygon, traversable by 2x2. (Note, the polygons do NOT need to be rectangles.)
  • Yes, when we have descructible terrain, we will need to recalculate the "chunking" polygons
  • You do raise a good point, When considering a 1x1 area, we need to check if the surrounding geometry will allow a 2x2 unit to fit. And mark accordingly.

 

Also, I realize I need to add a size element to combatants.xml, to indicate the 2x2 units.

So, stupid question, which ones are 2x2? I thought all the terrorist units were 2x2.

Edited by dteviot
Link to comment
Share on other sites

Guest Azrael Strife
Also, I realize I need to add a size element to combatants.xml, to indicate the 2x2 units.

So, stupid question, which ones are 2x2? I thought all the terrorist units were 2x2.

Terror Disk (Cyberdisk), Raptor (Reaper) and Tanks (all).

 

Spawn (Chryssalid) is a 1x1 terrorist.

Link to comment
Share on other sites

  • 3 weeks later...

The only 2x2 units in the game are the Tanks, Reapers, Cyberdiscs and Sectopods. Everything else is 1x1. ;)

 

Hmm, I wondered how we were going to handle large units a while back. In the original X-COM, the 2x2 units had a "primary quarter". If you had that quarter selected, you were able to navigate the large units up single width stairs or down a narrow corridor. It was a glitch obviously, but a fair work-around considering the alternatives. These alternatives are what we are trying to investigate. Perhaps we should just flag narrow stairs or corridors so that the large units cannot pass. But that doesn't solve pathfinding around terrain. ^_^

 

If 2x2 units are going to be a total pain, why not make everything 1x1 for v1.0? Nothing says we have to have large terror units. We could introduce them in later versions of the game if need be. :)

 

- Zombie

Edited by Zombie
Afterthought.
Link to comment
Share on other sites

Hmm, I wondered how we were going to handle large units a while back. In the original X-COM, the 2x2 units had a "primary quarter". If you had that quarter selected, you were able to navigate the large units up single width stairs or down a narrow corridor. It was a glitch obviously, but a fair work-around considering the alternatives. These alternatives are what we are trying to investigate. Perhaps we should just flag narrow stairs or corridors so that the large units cannot pass. But that doesn't solve pathfinding around terrain. ^_^

- Zombie

I'm not sure it's a glitch, it may be an artifact of how they did 2x2 path finding.

Which may have been, just do 1x1 path finding, using one quadrant of the combatant.

We could probably do the same thing.

Any complaints if we did the same?

Link to comment
Share on other sites

I'm not sure it's a glitch, it may be an artifact of how they did 2x2 path finding.

Which may have been, just do 1x1 path finding, using one quadrant of the combatant.

We could probably do the same thing.

Any complaints if we did the same?

The glitch is because if you selected anything other than the primary quarter, you were not able to get the unit up steps, etc. LOL I think it has to do with how large units were placed in the unit table (unitref.dat). Anyhow, I have no problems with a 1x1 approach, but I'm not the one programming it. ;)

 

- Zombie

Link to comment
Share on other sites

So would we just need to make maps allow 2x2 all the time because the model would be going through the wall otherwise?

Well, in theory that could still happen. The idea is while the unit is 2x2, for path finding it's treated as 1x1, Which means it could park the 1x1 next to a wall, with the other parts inside the wall.

Link to comment
Share on other sites

Couldn't you just have 1x1 pathfinding combined with a "don't go through walls"? In that, if a 2x2 followed along a 1x1 path but suddenly ran into an invalid move, it'd just stop and not go through a wall?
Link to comment
Share on other sites

Couldn't you just have 1x1 pathfinding combined with a "don't go through walls"? In that, if a 2x2 followed along a 1x1 path but suddenly ran into an invalid move, it'd just stop and not go through a wall?

If going to that much work (checking for walls, etc.) then you're basically doing a 2x2 path finding.

It's the same basic algorithm, A*, just that when you ask for "legal neighbours" to a given position, you need to consider if the move is legal for all the squares the combatant covers.

Link to comment
Share on other sites

It's the same basic algorithm, A*, just that when you ask for "legal neighbours" to a given position, you need to consider if the move is legal for all the squares the combatant covers.
So it's just a matter of performance? Why don't you try a version (maybe a new branch) and see how it works?
Link to comment
Share on other sites

It's the same basic algorithm, A*, just that when you ask for "legal neighbours" to a given position, you need to consider if the move is legal for all the squares the combatant covers.
So it's just a matter of performance? Why don't you try a version (maybe a new branch) and see how it works?

It's not even really a performance issue. Currently game engine does not spend a lot of time on A*. It's just that writing a 2x2 version of ListAccessbleNeighbours() (see http://svn.projectxenocide.com/xenocide/xn...Pathfinding.cs)

is going to take some effort. (due to extra wall checks, it's significantly more complicated.)

There also needs to be changes to the A* engine, so that it can be passed in a delegate specifying the ListAccessbleNeighbours() version to use. (And patches to the combatants class, so that they're aware of their size and algorithm to use.

There also needs to be changes to the set combatants to starting position code, change a combatant's position, etc.

Link to comment
Share on other sites

Maybe this is a totally stupid idea, maybe you are talking about this all the time and I just don't get it, but:

 

If pathfinding does not eat up a lot of resources, why not do 4x a 1x1 unit path and check if all the paths keep the same distance all the time.

 

Ok, this is not very sophisticated, and you might run into problems when trying to avoid a 1x1 object, but maybe it is good enogh for the beginning...

Link to comment
Share on other sites

Maybe this is a totally stupid idea, maybe you are talking about this all the time and I just don't get it, but:

 

If pathfinding does not eat up a lot of resources, why not do 4x a 1x1 unit path and check if all the paths keep the same distance all the time.

 

Ok, this is not very sophisticated, and you might run into problems when trying to avoid a 1x1 object, but maybe it is good enogh for the beginning...

 

Perhaps, if a 1x1 unit path exists, check the exact same path but with the other 3 cells as a starting position. If any of these is invalid (going through a wall or is not possible - ie, trying to go up a ramp where none exists) then the path is invalid for the 2x2 unit.

 

I mean, you already have a possible path which just needs to be checked 3 more times?

 

Does this make any sense?

Link to comment
Share on other sites

Maybe this is a totally stupid idea, maybe you are talking about this all the time and I just don't get it, but:

 

If pathfinding does not eat up a lot of resources, why not do 4x a 1x1 unit path and check if all the paths keep the same distance all the time.

 

Ok, this is not very sophisticated, and you might run into problems when trying to avoid a 1x1 object, but maybe it is good enough for the beginning...

This doesn't work.

Consider the following case.

Assume the cells of the terrain grid are like so

A0   A1   A2
B0   B1   B2
C0   C1  C2

etc.

Now assume we have a 1x1 unit at B1 that we are checking to see if we can move north.

So, we just need to check if can move from B1 to A1. (Which requires a number of tests, only one of which is "is there a wall between B1 and A1?").

Now assume we have a 2x2 unit on B1, B2, C1, C2 and we want to check if we can move north.

So, not only do we need to test if can move from B1 to A1, and from B2 to A2, but we also need to check that there is no wall between A1 and A2 (and that the difference in height between A1 and A2 is no more than 0.3)

 

 

Perhaps, if a 1x1 unit path exists, check the exact same path but with the other 3 cells as a starting position. If any of these is invalid (going through a wall or is not possible - ie, trying to go up a ramp where none exists) then the path is invalid for the 2x2 unit.

I mean, you already have a possible path which just needs to be checked 3 more times?

Does this make any sense?

Unfortunately, this also isn't going to work.

The main problem is that at least 50% of the time, if the path goes around a corner, the selected 1x1 path won't be viable for 2x2.

 

To explain. Assume you start path finding using the 2x2 unit's north west (top left) corner. Then, any time the unit needs to go around a corner where the unit changes direction from north to east, the checks will fail. The reason for this is A* will cut the path as close as it can to the corner, which will put the east (right) and south (bottom) parts of the unit inside the wall.

You'll also get invalid corner cutting if unit needs to go from north to west movement.

 

As I said before, the elegant solution is to take the cells, and convert them into larger regions, with the regions tagged if they can take or 1x1 and 2x2.

Having multiple ListAccessibleNeighbours() routines is the brute force approach.

Edited by dteviot
Link to comment
Share on other sites

As I said before, the elegant solution is to take the cells, and convert them into larger regions, with the regions tagged if they can take or 1x1 and 2x2.

Having multiple ListAccessibleNeighbours() routines is the brute force approach.

 

Never forget that the most innelegant solutions sometimes if coded correctly can be the most elegant of them all ;) ... instead of having the ListAccesibleNeighboars what you can do is define a "lambda" in C# 3.0. In C# 2.0 (what we are using) the syntax is a little more nasty, but can be implemented anyways. The solution is to have a delegate instead of "inheritance" where you give all the information to select if it can goes or not to the unit instead...

 

Suppose you can do something like this in the A*:

  • Foreach posible cell arround
    • if unit can move
      • evaluate certainty of movement

The trick is that unit can move can be parametriced as a Func delegate :). So you can do that without the A* algorithm notice that it is handling an special case. You can even go overboard and do that for the Foreach part of the statement too...

 

If you have any problem designing it, let me know and I can send you some example code that show the approach in action.

 

Greetings

Red Knight

Link to comment
Share on other sites

As I said before, the elegant solution is to take the cells, and convert them into larger regions, with the regions tagged if they can take or 1x1 and 2x2.

Having multiple ListAccessibleNeighbours() routines is the brute force approach.

 

Never forget that the most innelegant solutions sometimes if coded correctly can be the most elegant of them all ;) ... instead of having the ListAccesibleNeighboars what you can do is define a "lambda" in C# 3.0. In C# 2.0 (what we are using) the syntax is a little more nasty, but can be implemented anyways. The solution is to have a delegate instead of "inheritance" where you give all the information to select if it can goes or not to the unit instead...

 

Suppose you can do something like this in the A*:

  • Foreach posible cell arround
    • if unit can move
      • evaluate certainty of movement

The trick is that unit can move can be parametriced as a Func delegate :). So you can do that without the A* algorithm notice that it is handling an special case. You can even go overboard and do that for the Foreach part of the statement too...

 

If you have any problem designing it, let me know and I can send you some example code that show the approach in action.

 

Greetings

Red Knight

I think we're discussing the same basic idea, just different variations of it.

Have the FindPath() function. This implements the basic A* algorithm.

In A*, there's a "get the accessible neighbors of a location. i.e. Given a unit at cell (x, y, z), return a list of the adjacent cells the unit can move to.

There are two versions of this function, one version for 1x1, the other for 2x2 units. The function to use is passed into FindPath() via a delegate.

That's not a big deal.

The ugly bit is having to write two implementations of the ListAccessibleNeighbours() function. One for 1x1 and one for 2x2 units. The function isn't trivial. The 1x1 function currently in Xenocide is made up of about 20 functions.

Link to comment
Share on other sites

×
×
  • Create New...