hey guys, i''m new in AI, i''ve refer to books and come out with some path cost calculation and to get to the destination base on the path cost. i managed to get to the destination if the destination is constant. But i''m developing a game that requires the destination to be in dynamic. Every second the destination is changing and i''ve to get to the latest destination. it''s like a chasing game where one is going after the other. If to base on my path cost calculation the source is always a smaller number and the destination is a greater number. So i''m going from the smaller number to greater number. If the surrounding blocks is in same path cost i''m picking a random one. Here, i''m stuck, coz when destination changes i''m recalculating the path cost and the surrounding blocks always get the small number and it''s going round and round. Hope u guys can understand. evryone, pls throw some ideas to me, thanks!

How much effort do you want to go to in this project? Additionally, how much cheating information do you want to give your game agent? The method you implement will depend on your answers to these questions.

Cheers,

Timkin

dont know about him. but I am interested in methods without any cheating at all and I am willing to put efforts into it.

I am trying to write an good exploration bot, without using predefined waypoints.

at the moment, I am just testing out basic things: whenever I am running into some obstacle, I just turn a random degree until there is no long an obstacle in front me and continue moving forward.

yeah, it sounds really stupid and guess what it behaves really stupid too. it seldom makes out of the room, even when it does, it might gets stuck in corridors and never fully explore the map.

now, looking at Ages of King''s exploration, that''s more interesting. it actually does wonder around the map and explores every corner of the map, making clever obstacle avoidance. Are they cheating by using precomputed waypoints? Those maps are randomly generated, right? so any 1 have some good idea about how they did it?

Even in randomly generated maps the way-points can be pre-calculated.

Right now I'm working on a similar solution to the one you are looking for, so here's some ramblings on what I've acheived so far (the path finding is very fast, but I've yet to add any bots or the sensory stimuli necessary to make use of them).

My chosen way points are Points of Visibiliy, and their connectivity is kept in a look-up table (LUT) except, to keep the memory use down I decided to make a LUT class template that only creates one half of the table and all references to (row, col) where row > col, are re-mapped to (col, row). Surprisingly the overhead is negligable and it keeps maintenance very straight-forward as Path(a,b) is always the same as Path(b,a).

I chose Points of Visibility after reading some articles on Gamasutra, as well as A* path finding (with a little help from the people around here).

My scene is dynamic, in that the majority of objects can be destroyed which invalidates all the PoV's around it, and it can open up many other connections that were previously being blocked. In order to keep all this in real-time the connectivity LUT holds the number of "blockages" and the length (cost of this path). Each object in the scene keeps a list of all the paths it is blocking and when it is destroyed it decrements the "blockages" counter of each one. Obviously a path is not openly available until the number of blockages == 0.

Now I am happy with the path-finding I'm excited about the prospect of arming bots with this worldly knowledge- I will assume that they know their way around the initial level (since the object of the game usually involves attacking them on their own territory) but I'm undecided on how to evolve their knowledge of the topology as the player destroys objects, but the options are exciting and appear trivial to implement. The easiest option would be to let them all know, at any time, which paths are available. Alternatively, I could prevent them from knowing a path is open because they (or one of their comrades) haven't 'seen' the object which has been destroyed and therefore they cannot know that a particular path is open (so they'll have to rely on their initial knowledge to find their way around until they have seen the bloody great holes the player has put through their precious encampment walls).

I've really enjoyed this first venture into AI, but sometimes it has made my head hurt

Anyway, back to the PoV's.. Any route found consists of an arbitrary point on the map (start), zero or more PoV's, to another abitrary point (end). One difficulty I had was in finding a quick way to evaluate the best start and end PoV's (as one of my recent threads somewhere in here testifies) and guess what.. more precalculation was involved. I made a radial partitioning class, and every PoV on the map tests every object on the map for the minimum and maximum angles that the object shadows. Each shadowed region (or pie slice) is sub-divided until there is only a pre-set maximum number of objects (or less) passing through it. Now to test if any arbitrary point is visible from any particular PoV, the PoV first finds the angle from itself to the point, then finds the appropriate shadow region, and tests the few objects in there (if any) to see if they are acting as obstructions. Also, all the PoV's are stored in a Quad-tree structure which means I can easily find the closest POV to any point, so that's what I do. Find the closest POV to the start point, the closest to the end point, and then find a route between them. "Wait!", I here you cry, "the closest PoV's won't always be the best option!" - Damn right, but they are guaranteed to be obstruction free (ie There will be no objects between the Bot and the closest PoV) and I don't have to take the supplied route as my first choice.. instead I test against selected PoV's to see if the start point or end point is visible, if it is, cut out all the redundant PoV's from the head or the tail of the route (simple half-testing methods helped here, and remember I can detect if any point is visible from any PoV very quickly).

All-in-all my approach is memory intensive but fast (and still a little bit untested ). I'm not sure how much of this rambling is helpful but I've been wanting to get it off my chest ever since I first found it capable of route-finding it's way through 320 PoV's in 0.01 of a second on my old Duron 800 - it made me happy that the work was worth it, when I first had it running partially at less than one fps I was wondering just how much I had to do to make it real-time fast- the answer lies above.

Oh hum... It's back to the MFC level editor coding for me... barely as interesting as AI, but a necessary evil... thanks for providing me with a welcome distraction!

Cheers!

Matt


matibee.com

[edited by - 3dModelMan on July 24, 2002 3:44:24 PM]