iLikeThisGame

by the way here's the functioning link http://www.cgf-ai.com/slides_gdc2005.html

William, that's clever, it also surely needs far less ram to store the LOS table.

What i was saying in my post is that the LOS table should not be "scanned" tile by tile: in programmer's language that's called a linear search algorithm, and it's very very inefficient on such a large dataset. The best way to look for data on a table is by implementing a binary search algorithm: this kind of algorithm allows to you to find the information you need very faster. An example (trying not to talk too much like a programmer): on a 2km x 2km map, the 8x8 m grid is composed of 62,500 tiles (or Action Spots). For each of these tiles you have precalculated a list of tiles that can be seen from there, that's the LOS table. The algorithm Steve described is this: every unit checks all of the tiles who are in its "can see" list. Suppose you have 50 units, placed in 50 different tiles, we can assume that on average each of them can have in its list a number of entries who can be as much as 30,000 or so (it's just a rough estimate, and obviously this is dependent on the terrain and on unit placement, they'll be much less in urban settings and possibly more in open terrain). Let's just assume an average of 10,000 visible tiles for each unit. Now, if for every tile occupied by a unit you check all of the visible tiles, including empty ones, a full LOS table checks requires 50 x 10,000 = 500,000 iterations. Instead, if you implement a binary search algorithm, you can do the check this way: for each tile occupied by a unit, you consider all of the other tiles who have a unit inside, and check if each of them is contained in your "can see" list using binary search. Binary search is fast: it allows you to find an item in a list of 10,000 in only 15 iterations (or less), without needing to scan the entire list. So now the total number of iterations required is 50 x 50 x 15 = 37,500 Since at this level LOS can be considered working both ways, the actual number is halved: 18,750 (I'm still talking about checks to the table, without the need to compute any coordinates at all). So, the number of checks to do a complete LOS table check would be: - with full field of view scan, as described in previous posts: 500,000 - with binary search and direct tile-to-tile inquiry: 18,750 That is, in the second scenario you could iterate all the LOS table in only 5% of the time. With the time spared you can do more precise calculations based on the actual 3d coordinates, maybe even including checking obstruction to LOS from moving vehicles in real time (i'm not sure of this though). This gain of course heavily depends on how big the "can see" lists actually are as well as on the number of units, but surely when you have to find data in a list, and the list contains more than 20-30 items, binary search is the way to go. Obviously i don't know exactly how the game implementation works at this level: i'm just reasoning basing on Steve's description, and this is where my hypothesis can possibly be wrong. Surely Charles could put the final word on this. My idea is still that it was just the explanation to be inaccurate. Anyway, it's a great game, and getting better [ October 07, 2007, 06:16 AM: Message edited by: iLikeThisGame ]

I think the engine already knows which tile every unit is in, so it only needs to check the precalculated LOS table unit-tile to unit-tile, not every tile in field of view, and then possibly go on with more precise calculations based on actual situation. That is a very much smaller number of checks. Anyway the most probable thing is that the engine already works like this.. i think Steve was explaining it from a conceptual point of view, not explaining the actual algorithm.

Does this mean that every unit checks every terrain tile in its field of view, even if it is empty? Probably i am simply misunderstanding the explanation.. but if it's like that, aren't all those checks too many? The game engine knows already where all the units are, so it should only need to check LOS unit to unit. ... most likely i simply misunderstood anyway