A* Search in UDK - thoughts and advice?
Members - Reputation: 147
Posted 01 March 2013 - 06:29 PM
I'm making a computer game using the UDK engine, and it involves a simple scripted NPC in Unrealscript. I have much of its behaviours mapped out, but the core of its activity is going to be a search algorithm for the NPC to wander around the map until it sees something that makes it enter a function state.
1) A random world coordinate is generated to be the goal node.
2) Apply A* (or Best First) search to go to that coordinate.
3) If it sees the player, end the search and enter a ChasePlayer state
4) If it reaches the goal node, generate a new node and start again.
I'm no stranger to programming and I've worked with plenty of search algorithms several times in other projects, but never before in a game. My impression is that I'd be able to have a Searching state that contains the A* search algorithm written into code, and just go back and forth from there.
Now the main question - is there anything impossible or wrong with what I've just suggested? Is there something I should know about that'd complicate things in this way? I hear mixed reports about A* search in games, so I'd like to clear the air. Any advice you could give me would be hugely appreciated!
Crossbones+ - Reputation: 2506
Posted 02 March 2013 - 12:38 AM
I would recommend reading about AI already supported by the Unreal engine: http://udn.epicgames.com/Three/AIOverview.html and the Waypoints technical guide: http://udn.epicgames.com/Three/WaypointsTechnicalGuide.html
I think the FindPathTowards:
This function will execute a traversal of the path network generating a
route from the AI's position to the passed goal, placing the generated
route (An ordered list of waypoints from the anchor to the goal) in the RouteCache of the controller. This will tell the AI what waypoints to move to in order to reach its goal.
would already potentially implement A*.
If this is not what you wanted you could still maybe use the waypoints/Navigation mesh system for your code.
While A* "should" be able to be used in a 3D game (as long as you can place the nodes correctly), it might be good to implement some Steering behaviors as well. This seems like it could be tricky in three dimensions..
Here is an example:
Edited by shadowisadog, 02 March 2013 - 12:40 AM.
Members - Reputation: 147
Posted 02 March 2013 - 05:20 AM
shadowisadog, thank you very much for your reply! Steering behaviours like Seeking would be excellent, but I'm very unsure how to implement a library for a game, and given my tight deadline (19 days!) I would feel comfortable with a simpler, sure-thing approach.
On top of that, those links are related to Unity whereas I'm using Unreal, and I sadly can't afford the few days it'd take to fix anything that might go wrong. I'm aware of MoveTo and FindPathTowards, but the part I'm worried about is about node finding.
I could place some nodes in the game world for it to travel to, but what I'd rather do is get a variable that stores a randomly generated world coordinate and set that as the goal position, then create a new goal position to travel to whenever that is reached. I can see conditions I'd need to check for if I used that example (e.g. that coordinate is occupied by a static mesh), but is something like that possible?
Edited by Sammieo, 02 March 2013 - 06:03 AM.