Jump to content

View more

Image of the Day

The beast has a mighty searchlight of evil! #screenshotsaturday https://t.co/bzKepOojDL
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Sign up now

A* Search in UDK - thoughts and advice?

4: Adsense

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 Sammieo   Members   


Posted 01 March 2013 - 06:29 PM

Hey guys. Complete game development beginner, but I've been working on a final-year uni project for the better part of three months, and the pressure is on to finish it by the end of March.

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!

#2 shadowisadog   Members   


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.

#3 Sammieo   Members   


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.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.