Artificial Intelligence Depot
Visiting guest. Why not sign in?
News, knowledge and discussion for the AI enthusiast.
FEATURES COMMUNITY KNOWLEDGE SEARCH  
Genetic Programming : An Introduction
Imagine a world in which computers program other computers based on strategies borrowed from biology and natural selection. The book explores such fascinating possibilities thanks to AI!
More information at Amazon US UK

Reply to Message

Not registered yet?

The AI Depot has a focused community of friendly users. Rather than let anyone abuse the site at the brink of promiscuity, we prefer to let only those with an active interest participate... this simply requires registering.

Why not sign up!

Joining the site's community is completely free. You can then post messages freely, and customise your personal profile at will. Specific privileges will also be granted to you, like being able to access printer-friendly articles without restrictions. So, why not register?

Username:
Password:
Subject:
Email me when someone replies.
Body:

Parent Message

CGF

CGF intentionally does not autonomously learn the map. The bots together do learn the tactical value of waypoints (getting a tactical understanding of the is done both in-game and off-line, and any of them already has an effect).

Early on in the development of CGF, the bots were able to do some roaming and they created a waypoint graph on the fly. I tossed this functionality out for several reasons:

<ul>

<li>building a good map using solely roaming is quite tough in the Q2 environment</li>

<li>having the AI operate using incomplete information about the terrain, while also gathering more information is a large and interesting task in itself (as Alex demonstrates), but not one that coincided with my aims</li>

<li>most gamers don't want to fight bots that still need to learn the terrain; instead, they want opponents at about the strenght of their friends</li>

<li>exploring the terrain in-game takes away a significant amount of CPU (most of CGF was developed on a PentiumPro 200Mhz)</li>

<li>the roaming/mapping code and the changing terrain information dimensions would greatly complicate my (already) large design</li>

<li>investments in "auto-mapping AI" typically aren't appreciated by game developers, because they don't need it in their games (note that most Q3Arena engine based games do not use the off-line automated mapping (AAS) facilities included in the engine license)</li>

</ul>

William

19 posts.
Friday 01 March, 18:23
Reply
Map Learning

Regarding your 3rd point; it takes a bot significantly less time to learn a map than it does a human. Bots are very well suited to remembering stuff, and as long as the exploration scheme is reasonable -- it's acceptable in the demo, but the curiosity scheme I'm working on will make it better -- you can build up a map decent enough to embarrass a human player ;)

For the 6th point, that's true for deathmatch FPS. But assuming a more interesting storyline, with an AI character that progresses through the level as you move forward, it would be an amazing feature. For MMORPG to, pre-processing is rarely possible. The applications are far and wide ;)

935 posts.
Thursday 07 March, 21:11
Reply
some comments & questions

"Regarding your 3rd point; it takes a bot significantly less time to learn a map than it does a human."

I fully agree (although the bot might not autonomously gain the understanding that the level editor could give him using a few 'hint waypoint flags'). However, the problem is that if the AI needs to learn a map (and hence use incomplete terrain information), it is hard to write very efficient terrain reasoning algorithms on top of it.

Do you have an example of a MMORPG where I cannot do pre-processing (I don't play them, so I don't know much about them)?

19 posts.
Monday 11 March, 12:58
Reply
Embedded Agents

I don't play MMORPG either. Isn't it difficult to find time when you're a developer? Anyway, there are two cases where learning a terrain is essential -- aside just providing realistic human-like terrain exploration:

1) Huge static terrains, where pre-computing everything would take too much memory. You'd need forgetting for the bot to be able to cope with new areas, so learning goes hand in hand with it.
2) Parametrically generated terrains, they can be potentially infinite, and unpreviously seen -- allowing no processing. This applies if your bot is client side too.

Anyway, the navigation designed fits into my research approach to game agent AI, namely situatedness. The agent is embedded into its body (the animat), and cannot cheat by pre-processing or accessing unknown information. This is a bit of a hassle, and a lot of work to optimise, but possible and most definitely rewarding!

Though I would have agreed with your other points a couple month's ago, the quality of the maps that are currently been generated are amazing for terrain reasoning: they more than match the brute force waypoint placing thanks to the simplicity of the representation, and since they are iteratively corrected, they tend towards the perfect representation for the bot -- the best compromise between simple and useful.

Since your mesh is dense, you have to deal with information in a statistical fashion. With a simple representation, that can be done with vector arithmetic and graph operations. I'm polishing up the lower-level before I move on, but this is one of the things I'm intensely looking forward to (notably using a knowledge-based GA for topography based squad tactics).

There are a few problems with the discovery still, like finding all the places in Q2 'base1', as you said on flipCode. This can be done with really random discovery behaviours, or brute force wall following, but I don't like the way it's done at all. But once these problems have been overcome, the system's potential may be unleached ;)

935 posts.
Monday 11 March, 13:43
Reply
on large terrain and on your work

>Huge static terrains

Operation Flashpoint comes to mind... Impressive game. Should have received a number of awards...

This is exactly an area where pre-computing pays off. Keeping everything in memory is often not feasible (PS2 - not enough memory) or incurs significant overhead due to page misses and access to memory that had to be swapped to disk.
Precomputing all of the terrain's waypoints allows you also to partition the terrain representation into a number of overlapping areas. Only those areas that are necessary to support the AI characters would have to be loaded (rather than the full terrain description). And during movement, new area representations can be streamed/loaded from hard disk / optical disk. (Grand Theft Auto 3 does this with city geometry on the PS2 - perhaps it is a feature of the Renderware engine underneath).

I'd be curious how an 'on-the-fly' learning system would deal with an Operation Flashpoint situation.

(Frankly, I believe Operation Flashpoint does not use not either method, but basically navigates on the heightmap and a 2.5D mesh; the terrain is pretty much free of obstacles, and solely in a handful of buildings and in guard towers you can arrive above other accessible locations).

>[writing a paper]
If you need reviewers, I'd be glad to assist (since I'm curious what your approach can and cannot do). I guess I'm biased to my personal way of handling terrain, but at least I'm aware of that. And I'm used to reviewing papers...

William

19 posts.
Tuesday 12 March, 07:31
Reply
Different Approaches

On landscapes, it is true that very little terrain representation is required, as very simple reactive rules can get you around obstacles. This applies to towns aswell, but the more complex they get, the more a higher level of intelligence is required.

I'm sure the streaming approach would work, and having spent a bit of time on landscapes with static pre-computed LOD levels, I can foresee how that would be done. Consoles are well suited to background loading in such a way.

I guess I just like the idea of honesty ;) Until it comes crashing down on me that is!

The paper will be on the path planning only, as that is a topic big enough for a paper. I thinking of ask you to read it anyway, but a review would be even better ;) The execution of the motion, and the learning of the terrain will be inside my dissertation.

Cheers!

935 posts.
Tuesday 12 March, 08:23
Reply

Back to the Artificial Intelligence Depot.