2D-Plane data structure

I am writing an rts game engine in C++. Does anyone know of a good example of a 2d plane data structure for storing mobile units and fog of war?

Use this:

char mobile_units[];
char fog_of_war[];

ok fuckhead

Map: int **map;
Fog: see Map
Units: Map's x,y in a struct with other data.

Try again when you have an intelligent question.

　　　　　　 , ---　､_　　　 　 　 　 　 　 　 　
　　　 　 ／ミミミヾヾヽ､＿　　　　　　　 　 　
　　　∠ヾヾヾヾヾヾjj┴彡ﾆヽ
　　/ ,　-ー‐'"´´´　　　 ヾ.三ヽ
　 ,' /　　　　　　　　　　　　ヾ三ヽ　　　　
　 j |　　　　　　　　　　　　 / }ミ　i
　 | |　　　　　　　 　 　 　 / /ミ　 !　　
　 } | r､　　　　　　　　　　l　ﾞiミ __」　　
　　|]ﾑヽ､_　　　　__∠二､__,ｨ|/ ｨ }　　
　　| 　 ￣｀ﾐｌ==r'´　　 　 /　|lぅ　lj　　
　　「!ヽ､_____j　ヽ､＿　 -'　　ﾚ'r'/　　　
　　 `! 　 　 j　　ヽ　 　 　 　 j_ノ　　　　
　　　',　 　 ヽｧ_ '┘　　　　　,i　　　　　
　　　 ヽ　　___'...＿_　　 i 　 ハ__　　　　
　　　　 ヽ　ﾞ二二　`　 ,' ／／ 八　　　
　　　　　 ヽ　 　 　 　 ／'´ 　 /　ヽ
　　　　　　|ヽ､＿_,　'´ / 　 ／　　　＼　　

Dig this.

C++ map is a one dimensional data structure, just key->value pairs, so that's a stupid answer.

Each unit in an RTS with AI needs to be able to get a list of all other units in a certain radius of itself so that it can automatically detect enemies in its line of sight and move towards them to attack them, right?

So if I just use a map on X,Y then suppose a unit has a radius R of sight, to do its sight-check it would have to check on the order of O(R^2) squares around it. Multiply that by N, and we would have a shitty implementation.

So I'll repeat the original question. Does anyone know how this is ACTUALLY done in RTS games? Because the answers given so far are B.S.

Use a 2d array (array of arrays). How hard was that?

Try this line of thinking:

Use a linked list of Unit objects for each "team".

Each unit knows it's own X & Y position on the grid.

"Line of sight" could mean "Falls inside a box
around the unit doing the sight check".

The boundry box for some unit is (say): top left->(X-20,Y-20) bottom right->(X+20, Y+20). Baddie is in "line of sight"
if (baddie.X > X-21) AND (baddie.X < X+21) AND (baddie.Y > Y-21) AND (baddie.Y < Y-21) ...

Once you know a baddie is in "in the box" other calculations
become easy (ie. Is there an obstruction between the two
units, what path does a missile need to take etc...).

You don't need to to the sight check on units in the same
linked list as the one doing the sight check.

If you are looking to attack then you don't need to check
against units the checking unit is un-able to attack.

Hope this is helpful...

a quad tree is a structure you can use to check nearby units in much less time than O(R^2).

>>10 or just a grid, with squares that have sides of similar length to the maximum line of sight. Then when we have a specific unit we only need to check the squares around it.

Like what >>8 said, an array of arrays but each element would be a list of units contained in that square/cell.

A simple array of arrays of booleans should work fine for fog of war.

>>12
He's right

>>13
He's right

>>16
He's right

>>15
He's right

>>15,16

PIME TARADOX!

>>15
Likes it in the ass.

Implement fag of war

An array of arrays adds a layer of indirection. EXPERT PROGRAMMERS use a flat array indexed with x+y*WIDTH.

a layer of indirection? wtf does that mean?
mid-level programmers use x+y*WIDTH.

That you need to derefer two pointers instead of one.

Doesn't work if WIDTH is infinite.

WIDTH = infinite implies an infinite length array, which to me sounds really dumb. Anon, you are a strange person to be. You are a strange friend to have.

>>24
Not really, it's a very valid concern, you want to always make sure that your arrays can have infinite, zero and negative WIDTH.

You misunderstand. By using x+y*WIDTH you are essentially converting

 |---|---|---|
 |1,1|2,1|3,1|
 |---|---|---|
 |1,2|2,2|3,2|
 |---|---|---|
 |1,3|2,3|3,3|
 |---|---|---|
into

 |---|---|---|
 | 1 | 2 | 3 |
 |---|---|---|
 | 4 | 5 | 6 |
 |---|---|---|
 | 7 | 8 | 9 |
 |---|---|---|
which relies on one of the dimensions - the one whose range is represented by WIDTH - being finite. If both dimensions are infinite, this will fail to work.

>>26 lol.

By using x+y*WIDTH you are essentially admitting you are not a good enough programmer to make a generic, efficient 2d array.

>>28

LOL, troll

the main problem with the array is that it's gonna be big, like, proportional to the map size.

>>10 is right, a quad tree or another space partitioning tree is a lot better than a huge array

Does that mean it would be a bad idea to use an array to lay out my tiles in a 2D Pacman rip-off?

>>31
YOU'RE CRAZY DUDE! THIS'LL NEVER WORK

There's a difference between tiles and units. A 2D array is a good idea for tiles or fog-of-war, but a poor one for units.