http://img96.imageshack.us/my.php?image=screenshot036ry3.jpg http://img96.imageshack.us/my.php?image=screenshot037ya1.jpg The blue cross in the very middle is where I start, however I have no knowledge of the the points around me in the second image. The dark red squares are all I have to calibrate, the red lines at the end of green lines are a dead end, and the purple is my goal. I can move around the map and discover points, but eventually I forget where I am and sometimes go in circles. What's the best way to gradually path through something like this, and store previous points you've been at? EDIT: Forgot to mention the purple area was my goal. EDIT #2: Here's an example video of a project I'm modeling mine after:

I know of a few techniques used both in games and in robotics, but I'm not sure exactly what your problem domain is. What kind of behaviour do you want to emulate - are you wanting your A.I. agent to have a limited understanding of the world around it?

I'm also a bit unsure what you mean by the dark red squares being all you have to calibrate. Does this mean you're using these dark red squares as landmarks and have a map of where they are and how they relate to each other? Or does it mean that is all your agent can "see"?

Most pathing algorithms in games use the A* (A star) algorithm, but as far as I know that's if your agent has a predefined map of the world to navigate around in. There's a few robot techniques I know of that work in unknown environments but I figure most of them would be overkill for a software based game environment.

exploratory mapping.

The technique typically used for this process is SLAM. described here: http://en.wikipedia.org/wiki/Simultaneous_localization_and_mapping It's a technique for real-world robotic pathfinding which is basically the problem you describe (except your dead-reckoning will be able to be exact).

-me

Quote:Original post by Palidine
The technique typically used for this process is SLAM. described here: http://en.wikipedia.org/wiki/Simultaneous_localization_and_mapping It's a technique for real-world robotic pathfinding which is basically the problem you describe (except your dead-reckoning will be able to be exact).

While SLAM techniques are used for robotic pathfinding the common ones used in robotics today - Kalman filters and particle filters - are fairly likely to be overkill for a game situation. The difficulty in robotics comes from coping with the uncertainty in dead-reckoning and the sensors. If this is for a game then that won't be an issue and I'd recommend using something easier and faster than SLAM.

Of course, if you're simulating a robot, then I'd be happy to give some pointers on SLAM techniques. It's just I think there's a good chance they're not required in your situation. Plus the fact I'm a bit rusty on them myself - although personally I really have to get to grips with them in the near future for my non-game related programming activities [smile].

Basically I use the red "calibrate" points to tell which direction I should be heading, what I have been doing is going in a counter-clockwise direction, which doesn't work too well and gets me caught in circles regularly.

I'll research this SLAM stuff religiously, I'm very happy there's already some solutions for this kind of stuff :)

Thanks for the quick replies, guys.

EDIT: Reading the SLAM stuff, it seems it is WAY above what I want. I'll keep looking into this, though. Thanks again :)

EDIT #2: After about half an hour of research, I think I'm in way over my head. All the math symbols and such are just extremely confusing. I found LURCH and the Las Vegas algorithm, and understood them, but couldn't really relate them to my subject.

My main problem is finding a way to track the places I've already been, because I can't tell exactly how far I've traveled; however, maybe I _can_ tell how far I've traveled, if I use the nearest red "calibrate" point as a pivot, but I can't tell one from another!

EDIT #3: Here's my current plan, but I'm unsure of how to "track" all the points on the screen.

http://img206.imageshack.us/img206/8632/screenshot040copyrw1.jpg

[Edited by - Insolence on November 28, 2006 11:05:13 AM]

Bump, new information in my last post :)

Bump again :)

It's not clear to me what you actually need to do. I don't understand what you mean by 'calibrate' in this context, and I suspect that you're using the term in a way it doesn't usually correspond to.

I can't watch the video you posted, and I expect a fair few people won't be able to if they're posting from work or something, so a good description would help.
Are you just trying to systematically explore, until you stumble upon a goal? If so, I had a paper on this, but it's at home, so I'll take a look later.

I'm sorry, "calibrate" is simply one of the red squares that the green lines lead to.

"Are you just trying to systematically explore, until you stumble upon a goal?"
Exactly.

What I've thought about doing, is using some kind of linked list, that instead of just having a Previous and Next has Previous along with NorthWest, NorthEast, SouthWest, and SouthEast. That way I can uniquely identify each "calibrate" based on which points it leads to, instead of its Pixel X/Y on screen (which changes when you move around the map).

I think in this kind of scenario you could just apply Djiksta's algorithm.
You'd have to move the character to any node that you haven't already examined so you know which nodes are adjacent to it, but apart from that, it should still work.

Are you looking to automate a Diablo client or something?