Path finding/obstacle avoidance

To take care of obstacles that your agent can step over, simply slice horizontally through your world at their maximum step height to get a new 'floor plan' of areas that can be trodden.

quote:

---

So far the idea that I am thinking of is creating a frustum from the point of view of the agent's eyes when pointed directly at the target position

---

There was a Masters Thesis published last year and linked to through this site that dealt with this very problem. It may be in the articles and resources section... otherwise do a web search for scene analysis for games (or similar keywords).

The technicalities of discovering obstacles aren't particularly difficult. The harder task is to have your agent determine an appropriate course of action to avoid the obstacle, while still enabling it to reach its goal. Typically, a rational agent would like to minimise the cost of the deviation. However, there may be some uncertainty associated with whether or not the agent can return to its path on the other side of the obstacle. If the obstacle is a rock and the agent can identify this, then there probably isn't much uncertainty. If, however, the obstacle is a wall and there are two doors in the wall, the agent needs to choose which door to go through to get to the goal.

Now, your agent is currently dealing with steering behaviours. One way to keep it away from walls and obstacles is to penalise movement near them. That is, within the agents field of view (or within the map it has made of areas explored), designate floor regions with a higher movement cost. Have your agent always seek to move in regions of lowest cost. Once it detects an obstacle, assign a diminishing cost for floor regions emanating from the obstacle. The agent will then stay away from them. There was a paper quite some years ago that combined this idea with the distance transform algorithm for concurrent obstacle avoidance and path planning. I don't have the reference with me, but if you cannot find it online, I should be able to dig it up (although it might take some time).

As for the high level decision making, that is your toughest problem to deal with. You can just ignore it and have your agent choose randomly (for example, in the door problem above, flip an unbiased coin). However, there has been tonnes of research done in this problem area and so you would benefit from reading about solutions to Partially Observable Markov Decision Problems (POMDPs) and Robot Exploration tasks.

Good luck with your work!

Timkin

[edited by - Timkin on January 8, 2004 8:43:32 PM]

you may find this paper enlightening.

http://www.idsoftware.com/home/jan/q3abotai/Q3ABotAI_15.pdf



My Website: ai-junkie.com | My Book: AI Techniques for Game Programming

Thanks, I will look into some of your suggestions.

The movement costs for walking in certain areas sounds interesting, and probably easily adaptable to my current path-planning structure, I will definitely be tinkering around with it tonight. What I''m thinking now is subdividing a cell into areas like a quadtree of sorts, and assign cost values to each quad based on objects contained in the quad (parent quads may take on some kind of average of it''s children). Objects that can be walked over will be given a small weight, scaled by the heigh of their bounding box, and unpassable objects will be given a much higher cost. Then I can map several potential courses through the cell, and take the one with the cheapest cost. I can then add costs for quads that contain enemies, and things like that. Then perhaps I can take into account trickier situations, such as, if there is an enemy in the room, does the shortest path leave the agent vulnerable, in this case open areas would have a higher cost than they would otherwise (the quad in the center of the room may gain a cost similar to an impenetrable object).

The wall with 2 door problems I already have a basis for, since it is a portal engine and all doors are portals into the next cell, if the desired location is within the next cell it will already choose the door that will give it the shortest path to the destination. At a high level it is mostly precalculated: the cost of paths between every cell in the ''world'' is calculated against every other cell at load time. So if there are 25 walls between the object and the destination, the costs to travel from the starting cell to the destination cell through each portal is already known via Djikstra''s algorithm, so I take the distance from starting point to each portal in the current cell, and distance from destination point to each portal in the destination cell, and add those values to the paths that include those cells, and use that value to determine the path with the cheapest cost. I could probably break each portal up into an AABB tree of sorts, and precalculate from smaller chunks in each cell, but the memory usage would probably get out of hand very quickly in a large world.

The structure I am using allows me to take into account things other than actual distance, for instance if there are 2 paths with equal lengths, and one of the paths goes through a room that contains dangers for the agent, the path with the danger will have a higher cost. At runtime, some of the paths can be adjusted based on observations from the agent; if agent sees an adversary with a BFG run into a particular cell, and the current cheapest-path includes traversal through that cell, then it will add a danger modifier to the cost of that path, then get the costs of alternate paths and compare them. Ideally I would want to base most of the creatures decisions on an ''observed'' knowledge base, rather than an omniscient knowledge base. I have some ideas for updating the path-planning in realtime as the agent explores maps like everybody else, but there''s not enough going on in my engine to affect the agent''s motivation to move around yet.

I guess this is where my steering overlaps with my motivation, because the shortest-path planning structure allows modifications that would be made at the motivation level. I could probably add an intelligence modifier in there to fuzzy the solution a bit, so that agents with a higher intelligence rating have a better chance of choosing the best path than agents with a lower rating. Likewise, a *bolder* agent may give less weight to the danger modifiers (a stupid, bold agent may invert the modifier and choose the most dangerous path every time) than a coward, who may always take the safer path even if it is twice as long. The current health, ammo supply, state-of-mind (belligerent, aggressive, cautious, confused), etc, may also affect the modifiers.

And I could go on all night, lol. Gotta get the obstacle avoidance down before I get into all of that. It''s all been churning in the back of my mind for a while as I sludge through the other stuff.

Anyway, thanks for the input, I''ll be googling a lot tonight

Peace