Artificial Intelligence Depot
Visiting guest. Why not sign in?
News, knowledge and discussion for the AI enthusiast.
FEATURES COMMUNITY KNOWLEDGE SEARCH  
Get Creative: AI Article Writing Contest
Fancy the chance of getting developer focus, improving your research skills, sharing your artificial intelligence ideas, obtaining expert feedback, getting published online AND winning a prize?
Enter the AI Article Writing Contest!

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

path lengths, not the paths

Alex, thanks for the reply and clarification.

I'm not sure we're discussing the same problem. My statement is that when you complete your AI into a full blown game AI, the main demand for paths is about path lengths, not the paths themselves.

Full blown bots will spend much of time (and code) in considering alternatives (should I take cover, attack, get a power-up, get the flag, camp here, join up with teammate x,y,z, etc.). Nearly every evaluations of such alternatives requires 'distance' information: is there any cover available with 2s distance, can I get to the threat quickly, is there any power-up nearby, who is the nearest teammate, etc.
In evaluating the alternatives, the exact path does not matter. Only when an alternative is chosen, the exact path is retrieved.
In other words, what the AI really needs is a (very) efficient way to estimate distances between his position and (almost) arbitrary locations on the map.
An AI design that is purely based on dynamic pathfinding (such as A*) will not be very efficient at these distance evaluations. Something closer to lookup tables and caches is required.

Your design sounds very interesting, and it's the first time I've seen concepts like plasticity being used. You also address the problem of optimizing a path towards multiple goals (TSP like).
But from what you describe, I cannot tell whether it is aimed at rapid pathfinding or rapid distance lookup, or both.
Do you have any numbers for "Firstly, it can return after any amount of time" (which I assume refers to the algorithm's ability to provide early results, rather than an absolute time).

For reference, on a PIII/500MHz, I could do over 5,000,000 distance lookup/s, whereas I could do solely ~1,700 A* path searches. (The earlier posted difference between A* and path lookup was incorrect, and should be a factor 2,000, not 200).
This factor 2000 is the difference between freely estimating distances everytime and everywhere it is needed in the AI (implementation), and on the other hand introducing complex caching and a resource manager (with queues to handle excessive requests posted in one frame) for A* path lookup.
Obviously, standard path lookup tables become cumbersome once you have over 1,500 waypoints/areas/cells/...

William

19 posts.
Friday 08 March, 04:26
Reply
Speed Tests

The cache also has distance values (or travel-time, or cumulated cost), so the penalty for a query is simply an array lookup. I'm in the process of reducing the memory overhead for each node -- there's few nodes anyway, but every little helps.

I'm going to write a paper about it for the ICCG. I've no idea if this is the sort of thing they are looking for, but it's definitely a good opportunity to do lots more testing.

Cheers for the interest ;)

935 posts.
Saturday 09 March, 11:09
Reply

Back to the Artificial Intelligence Depot.