Skip to main content
gamedev.net
🔒 Locked

Path-finding question

Started by Evig Dec 26, 2004 at 8:27 AM 2 replies 1k views
Original Post
Evig
Evig
Merry christmas to you all! Anyway, I'm currently developing a game server and I have a question for the AI gurus out there :p It's about the monsters, which I want to walk next to the player and then attack them when they are near enough. The thing is, the players on the server are almost always moving so it would be a big waste of resources to calculate a full path to the player everytime and then recalculate it when they move. What I want is basicly some algorithm that can make reasonable good guessing moves to find the player(I'm not sure what that's called, but isn't it called a heurestic function or something in the likes?). So instead of having the full route calculated, it only calculates the best spontaneous next move. Am I making any sense at all? Heh I hope so :P If that algorithm doesn't exist, then can anyone suggest some good fast, fairly accurate method of finding the path? I would be very grateful if anyone could link me to an article or to a sourcecode or perhaps explain or give me the name of some algorithm that can do good reasonable guessing of what direction to move to. Thanks a bunch :) /Evig
Kylotan
Kylotan
I'd probably attempt to use a bounded A* search here, and by this I mean setting a maximum path length that is significantly smaller than your map. Providing that the terrain is mainly open, rather than mazelike. Providing there are no big dead-ends, such a search should always take the monster in roughly the right direction. The main benefit of course is that you can reuse the A* algorithm for the search whether the player is near or far.

If you're not already using A*, I suggest you look into it, as it's a very versatile algorithm and given the right parameters, can probably solve your problem.

Another alternative to bounding the search - and which is probably overkill for you, but very effective nonethelesss - might be to pre-process the map, laying down some waypoints (probably at random), and precalculating paths between them. Then to find your way across the map, all you need to do is find a path to the nearest waypoint, and then use the predefined paths to get to the waypoint nearest the player. I've heard this approach referred to as a 'roadmap' and it seems to work well in many cases.
Evig
Evig
Thank you very much for answer :)

I haven't really read into A*, just some small descriptions of it. I thought it was really advanced and kind of overkill for my monsters.
I'll look into it now and see how it goes. :)

/Evig
Timkin
Timkin
Or use a very simply steering behaviour coupled with an obstacle avoidance behaviour for each NPC.

Timkin

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.