Article 3216 of comp.ai.games: From: nak@gwe486.cb.att.com () Subject: Re: "Seeing" you opponent - And some AI stuff. Organization: AT&T GBCS/Bell Labs Date: Wed, 6 Dec 1995 16:10:56 GMT
Rune Espeseth wrote:
: The players are on a field which has walls, all of : which is stored in an array. I want to display player : 2 to player 1 ONLY IF he is visible (i.e., there are : no walls in the way). I obviously have all the information : that I need, but things get a little messy when I deal : with non-cardinal directions, especially like : north-by-northeast, etc.Hmmm... This is just an idea: What about “drawing” a line from player 1 to player 2, checking each block on the way. If there is a wall “block”, there is no player in sight. If not, all is clear...
Well, just an idea...
Rune Espeseth
The general Line of Sight (LOS) problem is a bit of a bear. There are a number of issues....
- LOS paths must be reflexive.
That is to say that the path from A to B must be the same as from B to A. In a floating point world, this is usually “free” in that the rounding tends not to make differences in path. Floating point is slow, and it makes the computational complexity of LOS a real serious CPU hog. In an integer world of squares or hexes, you must FORCE rounding to behave in a reflexive manner or you will get times where A sees B but B can not see A. If your players detect this, they will complain *bitterly* about how unfair it is.
What I did in my hex based game was to always compute the path the same way regardless of endpoints. For example, say from the unit with the lower terrain array subscript to the higher. The endpoints are dealt with on a seperate basis since I can see out of the weeds I’m hiding in more easly than you can see into them.
- LOS is expensive computationally for unconstrained terrain.
For N objects you ray trace N-1 rays from each with a step size based on the minimum size of a terrain feature. If your terrain is squares or hexes, the step size is the path length in hexes along the LOS path. SO the total complexity is N * (N-1) * AverageRange.
Even in integer worlds, this can get expensive quickly. You can add constraints, such as limits to how far away a unit can be seen say due to terrain or darkness and lack of activity from the target.
I tend to have cover be an attribute and different terrains have varying amounts of it. The LOS ray accumulates cover until too much of it blocks further view and the ray terminates early.
- You may want to differentiate the “can see” attribute from “has LOS”.
If it’s dark and we both are being quiet, neither of us have can see but both have LOS. LOS is generally reflexive - if your units “sees” from the same altitude it “fires” from and “takes fire at” then it is always reflexive. Infantry usually work this way, but a tank might not; the tank commander is higher than the main gun is higher than the body of the tank.
Can see is not reflexive if I am hiding in a terrain that I can see out of more easily than you can see into. Tanks in the treeline see out better than spotters see in.
Can see might not be reflexive if my tank commander is standing on top of the turret of a turret-down tank behind a ridge line.
- Not explicitly stated above, but implied, is that you need an algorithm that walks LOS paths bewteen arbitrary points in the game.
- Try to avoid the N* (N-1) as much as possible if you have large N.
One way is to state “friendly units never bother to compute LOS or can see.” This attacks the N-1 term, which is a Good Thing (TM).
Another way is to restrict the units that participate in the computation. Head quarters units, for example, and indirect fire units might only care about units very close that could attack them. This cuts the N term, another Good Thing.
--- and now a point that returns towards AI.
- Constrained or Algorithmic terrain.
One way to speed up LOS is to have the terrain be divided into regions. A given hex can be in multiple regions. The region data for the hex will indicate if the hex is in a region or not (one bit item per region). It will also indicate if it can never have LOS to each region or it might be able to have LOS to that region (one more bit item per region).
This is a tradeoff of space for time. You are effectively storing the results of earlier computations for lookup.
You do a quick check; go throught the regions each hex is a member of and check the conditions.
For example, a ridge is don’t care to region A and B both and it is in both regions. The west side of the ridge is in region A. The east side of the ridge is in region B.
All NON-RIDGE hexes in B are marked NO LOS with regards to A. And for all non-ridge hexes in A, there is a marking NO LOS for region B. The ridge hexes are marked don’t care a-b b-a.
If neither unit is in a region, it doesn’t matter. If both are in a region, it doesn’t matter. If one unit is in a region and the other unit is not in that same region, then there is no LOS.
The regions can be computed a-priori and tuned during play for any given map. They give you a quick weeding function to keep you out of the LOS computation. This assumes that the ranges /step counts are high enough to be more expensive than the look ups. Given that LOS is math oriented in rising and falling terrain, it’s a good bet.
AI stuff:
Regions are very useful for your AI. Consider regions as nodes on a graph. (A slight redefinition of regions may be happening here). For example, the terrain of the day has a bridge over the Rhine river. The land on each side of the river is in a different region. My AI wants to get over the river. The lookup now is more complex; I use the two regions I’m in as indicies into a “path helper” data area. The Path helper data says that the best N ways to get from region 1 to region 2 involve first heading to this bridge.
My normal AI code tended to get to the river bank “and wimper” that it could not cross the river to get to the enemy it wanted to engage on the other side. Now it can know that it has to head to the bridge first.
The great power here is that you compute this stuff BEFORE HAND and you can TUNE IT before release. It costs you the ability to fight on arbitrary terrain, unless you can write the code to analyze terrain into regions to load the helper area. I haven’t gotten that far, but I’m sure that rudimentary tools can be developed for your given types of terrain features. It gives the AI a “home field” advantage that does not involve “cheating” unless the idea of having a map to study before hand is cheating.
---
Neil Kirby DoD# 0783 nak@gwe486.cb.att.com
AT&T Bell Labs Columbus OH USA (614) 860-5304
President Internet BMW Riders
The BMW R1100RSL - Because the Britten V 1000 is not street legal.
Reply from Eric Dybsand
From: edybs@ix.netcom.com (Eric Dybsand) Newsgroups: comp.ai.games Subject: Re: "Seeing" you opponent - And some AI stuff. Date: 7 Dec 1995 14:12:59 GMT Organization: Netcom In <DJ6AAA.38p@nntpa.cb.att.com> nak@gwe486.cb.att.com () writes: | [nice points on LOS snipped] |AI stuff: | |Regions are very useful for your AI. Consider regions as nodes on a graph. |(A slight redefinition of regions may be happening here). For example, the |terrain of the day has a bridge over the Rhine river. The land on each |side of the river is in a different region. My AI wants to get over the |river. The lookup now is more complex; I use the two regions I'm in as |indicies into a "path helper" data area. The Path helper data says that |the best N ways to get from region 1 to region 2 involve first heading to |this bridge. | |My normal AI code tended to get to the river bank "and wimper" that it |could not cross the river to get to the enemy it wanted to engage on the |other side. Now it can know that it has to head to the bridge first. | |The great power here is that you compute this stuff BEFORE HAND and you can |TUNE IT before release. It costs you the ability to fight on arbitrary |terrain, unless you can write the code to analyze terrain into regions to |load the helper area. I haven't gotten that far, but I'm sure that |rudimentary tools can be developed for your given types of terrain |features. It gives the AI a "home field" advantage that does not involve |"cheating" unless the idea of having a map to study before hand is |cheating. |
Hi Neil,
You have some good points on LOS, however I’d like to jump to the mention of use of regions in pathfinding.
The use of regions, or hex/cell groups, is a pathing approach that I’ve considered in the past, and tried and thrown away and re-considered, and re-tried, and thrown away again, all because of the problems of dealing with them in a dynamic map generating game. In other words, I’ve not been able to get good performance (as good as my old modified A* approach) when the map changes from game to game, and the AI must spend the cycles to generate the regions for use in later pathfinding.
Also, I’ve found regions to be somewhat less accurate, when the terrain of the map is widely dispate (ie. varies extensively within regions).
Have you had enough success in using regions during pathfinding to perhaps address some of these issues?
Regards,
Eric Dybsand
Glacier Edge Technology
Glendale, Colorado, USA
Reply from Neil Kirby
Newsgroups: comp.ai.games From: nak@gwe486.cb.att.com () Subject: Re: "Seeing" you opponent - And some AI stuff. Organization: AT&T GBCS/Bell Labs Date: Fri, 8 Dec 1995 15:56:52 GMT Eric Dybsand wrote: |In <DJ6AAA.38p@nntpa.cb.att.com> nak@gwe486.cb.att.com () writes: | |[nice points on LOS snipped] | |>AI stuff: |> |>Regions are very useful for your AI. Consider regions as nodes on a |graph. [snip] |You have some good points on LOS, however I'd like to jump to the |mention of use of regions in pathfinding. | |The use of regions, or hex/cell groups, is a pathing approach that |I've considered in the past, and tried and thrown away and |re-considered, and re-tried, and thrown away again, all because |of the problems of dealing with them in a dynamic map generating |game. In other words, I've not been able to get good performance |(as good as my old modified A* approach) when the map changes from |game to game, and the AI must spend the cycles to generate the |regions for use in later pathfinding.
Hi Eric!
I suspected that this would be the case. So far, all I’ve done is to set up the regions BASED ON FIXED TERRAIN. Terrain, in the game that I have good AI in, is fixed. You get to pick which map you fight on, but it is fixed.
Playtest gave us the most useful regions. The Rhine river bridge example was clearly a big win. The analysis was first done by hand and then I started working on analysis tools. I hit the same wall you did, that the analysis requires a human to be effective. Thus I was glad that I didn’t have to trust the machine to analyze an unknown map. I haven’t had good luck with machine generated terrain, so I was not heartbroken. part of the “artwork” of making a map includes playtest and analysis for choke points and regions.
This stuff keeps reminding me of field theory (and heat tranfer), back in the dark ages of my EE undergrad. If I had a better handle on the math, I might be able to make a conceptual breakthrough. Surface normals and that type of thing on a 3 dimensional surface... You can never have too much mathematics.
I have heard of “algorithmic terrain” which is generated so as to have along with it an algorithmic way of doing shortest path.
|Also, I've found regions to be somewhat less accurate, when the terrain |of the map is widely dispate (ie. varies extensively within regions).
Yes, the Manhattan map defied analysis. Skyscrapers next to Central park next to two story and one story buildings with water on three sides of the island.
|Have you had enough success in using regions during pathfinding to |perhaps address some of these issues?
Only to add to what you note. “Gentle” terrain that looks like it came from a real map, tends to work well. The rivers and roads stand out clearly as the obstacles and connectors. “Rough” terrain, like our Manahattan map, just gave us fits.
There’s a note of realism here. Armies do get lost in cities. And in rolling hils with rivers, roads, and bridges, it’s pretty “realistic” to come up against a river and then go find the bridge. And it’s also pretty realistic to tend to follow the road, since it is supposed to go somewhere.
I tend to view the situation as providing “help” to a normally reasonable ai setup that can usually get from place to place adequately. I tend to stay at a low level tactical sim where each unit has pretty decent, if never inspired, capability.
I view the “screwups” as the generator of “bad luck” and “mistakes” that somewhat resemble fog of war. This contrasts with the behavior code which while never inspired has had all of the newbie mistakes improved out of it. Most players seem to enjoy fighting a competent oponent suffering C3I troubles. That way the combat was a hard enough fight to be worthy of the effort, but you knew that if you had a plan and could execute it you would prevail.
I just yesterday got notified that I’ll be a speaker at the 1996 Computer game Developers Conference, so I’ll be there.
---
Neil Kirby DoD# 0783 nak@gwe486.cb.att.com
AT&T Bell Labs Columbus OH USA (614) 860-5304
President Internet BMW Riders
The BMW R1100RSL - Because the Britten V 1000 is not street legal.
Reply from Eric Dysband
From: edybs@ix.netcom.com (Eric Dybsand) Newsgroups: comp.ai.games Subject: Re: Map AI (was Seeing your opponent) Date: 9 Dec 1995 14:52:59 GMT Organization: Netcom |I suspected that this would be the case. So far, all I've done |is to set up the regions BASED ON FIXED TERRAIN. Terrain, in the |game that I have good AI in, is fixed. You get to pick which map |you fight on, but it is fixed.
Yes, that is advantage. However, as I discuss below, having to find fast, good pathfinding on a map generated at the start of the game (ala Empire, and the game I currently working on) is IMHO very difficult.
|Playtest gave us the most useful regions. The Rhine river |bridge example was clearly a big win. The analysis was first |done by hand and then I started working on analysis tools. I |hit the same wall you did, that the analysis requires a human |to be effective. Thus I was glad that I didn't have to trust |the machine to analyze an unknown map. I haven't had good |luck with machine generated terrain, so I was not heartbroken. |part of the "artwork" of making a map includes playtest and |analysis for choke points and regions.
Actually, with this current game project, I’m very impressed by the map generating algorithm. It consistently produces large, and realistic (IMO) terrain combinations.
However, when I applied a regionalized analysis to even a small map, the disparity of terrain within a region, and the time that was needed to analyze even a small world, was way too long to be practical and performed during game start up.
I agree with your comment about analysis being more effective with playtesting and a human involved, but alas, I can’t count on the player doing the work for me when s/he starts a game <g>.
Since you mentioned choke points, I’ll throw out 3 more questions for you to consider.
What is the fastest way you can think of to find coastlines when you are given a point on the landmass between them?
What is the fastest way you can think of to determine if the land mass you are located on, is an island, completely surrounded?
What is the fastest way you can think of to locate choke points that involve land vs. water?
Did you note, my common requirement, speed? <g>
|I have heard of "algorithmic terrain" which is generated so as to have |along with it an algorithmic way of doing shortest path.
That sounds interesting. Do you recall where you might have heard it?
|Yes, the Manhattan map defied analysis. Skyscrapers next to |Central park next to two story and one story buildings with |water on three sides of the island.
A wargame set in Manhattan? Well, that might be fun!
|Only to add to what you note. "Gentle" terrain that looks |like it came from a real map, tends to work well. The rivers |and roads stand out clearly as the obstacles and connectors. |"Rough" terrain, like our Manahattan map, just gave us fits.
Yeah, and add to that slopes and altitude effects and you just about described what I’m battling. Oh, and did I mention that it must do everything very fast?
|And in rolling hils with rivers, roads, and bridges, it's |pretty "realistic" to come up against a river and then go |find the bridge. And it's also pretty realistic to tend to |follow the road, since it is supposed to go somewhere.
That’s true.
|This contrasts with the behavior code which while never |inspired has had all of the newbie mistakes improved out of |it. Most players seem to enjoy fighting a competent oponent |suffering C3I troubles. That way the combat was a hard enough |fight to be worthy of the effort, but you knew that if you had |a plan and could execute it you would prevail.
True again. My philosophy has always been to strive for an entertaining opponent, given that with the computer cycles available on the consumer PC, the state of the art of computer AI today, and the facts that the human still has the best wetware known today and the ability to save/restore around unsatisfactory outcomes while learning how to win, that just entertaining the human player is a success. Actually beating a good human player, consistently, is still a ways out, IMHO.
|I just yesterday got notified that I'll be a speaker at the |1996 Computer game Developers Conference, so I'll be there.
Great! Since Miller-Freeman is doing it this year, I expect we will see more ‘for profit’ changes in the format and costs. I’ve been looking in the mail for the announcement for the early bird sign-up, but it hasn’t come yet.
I’ll try to make your talk this year. Will you be covering AI?
Regards,
Eric Dybsand
Glacier Edge Technology
Glendale, Colorado, USA
Reply from Roger Larsson
From: eplrl@eua.ericsson.se (Roger Larsson) Newsgroups: comp.ai.games Subject: Re: Map AI (was Seeing your opponent) Date: 12 Dec 1995 13:48:54 GMT Organization: Ericsson Telecom Systems Labs, Stockholm, Sweden Eric Dybsand (edybs@ix.netcom.com) wrote: : In <DJ9yyt.CLB@nntpa.cb.att.com> nak@gwe486.cb.att.com () writes: : > : > [part deleted] : : > : >Playtest gave us the most useful regions. The Rhine river : >bridge example was clearly a big win. The analysis was first : >done by hand and then I started working on analysis tools. I : >hit the same wall you did, that the analysis requires a human : >to be effective. Thus I was glad that I didn't have to trust : >the machine to analyze an unknown map. I haven't had good : >luck with machine generated terrain, so I was not heartbroken. : >part of the "artwork" of making a map includes playtest and : >analysis for choke points and regions. : > : Actually, with this current game project, I'm very impressed : by the map generating algorithm. It consistently produces : large, and realistic (IMO) terrain combinations. : However, when I applied a regionalized analysis to even a small : map, the disparity of terrain within a region, and the time that : was needed to analyze even a small world, was way too long to be : practical and performed during game start up.
Hi,
With all these new operating systems out there (OS/2, W95 ...) is it really necessary to make this analyze “at game start up”?
Start a thread to do the analyze during the game - people tend to think a lot in this kind of game and will probably start by doing a map analyze...
By prioritying in what order to analyze you could probably do your first movements without full knowledge.
What do you think about this approach?
/Roger L
Standard disclaimer...