for the heck of it i've been writing a basic tile engine with some basic graphics to play around with some AI. everything is going well so far. have units able to randomly walk around using paths generated by the pather and am starting to work on making them a little smarter looking. anyway the hurdle i'd like to hear some input on is AI units sighting other AI units. i have no problems with getting distances and line of sight and all that. my problem is how to check if other units are in sight and not have it ridiculously slow? obviously i dont' want to check every unit against every other unit. if i have 200 units that'd be 40,000 checks if i check each one. so the ways i've tinkered around with in my head are to have each tile hold a "who's looking at this tile" list. whenever a unit moves it updates what tiles hold it's name. then whenever a unit steps upon that tile an "alert" message is given to the unit who has that tile in sight. sounds neat in theory but seems overly complicated. plus i'd have to have a large available list per tile OR have it dynamic (which would be a LOT of newing/deleting of nodes. so that seems like a bad idea.) another thought was to just have a preset mask of tiles that i can apply to each unit's position to check tiles around it. this sounds good but that'd require templates for every size view radius (which isn't so bad i suppose). yet another is to have some dynamic way of getting tiles within a fixed radius so i could vary the size per guy or vary it on the fly in case say.. he drops his glasses or something . possibly check a dirty rectangle first to throw out obvious ones (this could be applied to all of the ideas). seems to be slow to generate masks on the fly though. only other idea was to have a fixed radius for all units and only check sights whenever one of them moves. he will check his new radius against other units and when he detects one he recieves a "sight" message and also gives the unit that he sees a sight message. i hate this idea though because of fixed radii. or maybe i'm way over examining this . any input from someone who's done anything like this would be much appreciated. i'd post in the AI forum or tile but i don't think much traffic goes in them. [edited by - sporff on March 27, 2004 1:48:41 AM]

sounds like somethings i''ve already done:

click for larger image

My game works with sides, that is, you are one team or the other, up to 6 in the game.

The "Map" class has an std::map in it that maps a team_id to a visibility value, for each tile. It''s sounds overly compilcated but its not.

When units move (turn based) they completely recalculate the visibility of the whole map.

foreach unit {
make the radius around the unit visible
}

of course, each unit takes LOS into account. However, the visibilty of a unit is the ( key concept: ) combined visibility of the entire team, not the individual.

So basically, my map class stores visibility, not the units. To make it simpler, if any one of your units can see the enemy or a tile, it counts for everybody on yourside. (chalk it up to "sharing of knowledge")

If you''de like source code you can ask, but it''s not a small game anymore.

ya, they have a field of view also of course and will only see things in line of sight but my steps were going to be discard all possible units with fast algorithms, then check within a real radius of who''s left and discard some more who aren''t actually in range. then do LOS and FOV checks to see if it can really see them. so if i was doing the mask idea i was going to apply the mask to the position and then when a hit is detected, check LOS and FOV and whatever else i need to as the last step.

leiavoia: having a stored list of guys "looking" at that tile was sorta the same as your teams list per tile of what team can see. i was originally gonna go strictly team based combat but this is evolving into more of a "throw a bunch of guys in the world and see what happens" kind of thing and not so team based. for example, i''m gonna add some fuzzy natures to the way they act so they don''t just hate or like someone. they can medium like someone and then maybe something they''re wearing or something they say also increases hatred past a certain level that that unit will attack or do something hostile towards them. there WILL be teams till but i''d think of it more as factions i suppose. their alliances will add to how much they are hated by certain characters. otherwise it''s a great idea you used. BTW... what was your game''s premise and play like? looks interesting.

thanks for replies. anyone else like to throw in their thoughts too?

i''m trying to avoid adding something like quadtrees to partition it up. i suppose i could possibly add that later though? i have the whole map object all set up at the moment and it works like a charm so i don''t really wanna go back and change any of that. i''m thinking i could add it as a secondary piece of information that just points to the map structure. and maybe each world node could contain a list of entities within it. that would be fine for speed becuase they wouldn''t constantly be walking over node boundaries so the map object wouldn''t be having to allocate/release a bunch of memory all the time.

for the time being i think i''ll toss something together since the entity class i''m using right now is [mostly] temporary. see how it handles things and then try different ways.

good replies so far. thanks.

For my game, the structure just maps an ID number (id of a team for instance, or anything else you care for. You can map each individual unit if you give them all unique IDs) to a visibilty level. Because i store it in an STL map, it looks up fast by key (ID). So, you can have teams or factions or units or whatever grouping you darn well feel like. But this sytem really works best when you can put units into some sort of group. Otherwise, i''d find some other structure.

My game is an abstract TBS game. It''s completely original. Basically the concept is to program units and let them do the rest. It''s very hands off. You simply assign them missions and they try to go about it as best as they can with their meager little AI brains. The strategy is the management of the units. Of course, the AI has to deal with the same shortcoming the units have. It''s roughly ~40% complete as games go (not fully playable but very tinkerable)

http://www.project-axis.net/

i have something like this: (pseudo code & munged so the forums don''t screw with the lt/gt)

struct world {
list(unit) units;
vector(vector(tile)) tiles;
}

struct tile {
types_enum type;
unit* myunit;
}

struct unit {
unit_enum type;
int x,y;
void move(int nx, int ny) {
world.tiles[x][y].myunit = 0;
x=nx; y=ny;
world.tiles[x][y].myunit = this;
}
}

And then, Detecting units is exactly the same as exploring terrain. if the unit can see that square, it can see the unit on that square.

Nothing terribly difficult about that... i don''t think...

Here''s mine from my map.h file:

	/** Maps axis IDs to a visibility state (used for each map tile)*/	typedef std::map<int,int> vismap;	// map tile structure - the main gig	class maptile: public MapSpecialsReserve {		public:			obstacle obst; //obstacle type			short int road_q; // road quality. 1-10, 10 = rough new terrain, 1 = well traveled road / fast.			Pod* occu; // the pod that occupies this tile			vismap vis; // 1=visible, -1=fogged(default), 0=invisible		} **the_map; // the map pointer-pointer array