Archived

This topic is now archived and is closed to further replies.

JoeMark

AI Pathfinding for text adventure

Recommended Posts

Hello. I''m trying to visualize how this is done and would appreciate any help. I''m coding a text adventure and need to have someone roam around the house however trying to write an algorithm (preferably small and simplistic) in which the AI can logically deduce the shortest route to any particular room via the one he or she is currently in. A few ideas spring to mind... such as using the hallway as a central focal point however then what makes that tough is that the rooms need to be all joined to the hallway in some fashion without breaching out. Any ideas/thoughts?

Share this post


Link to post
Share on other sites
A* would work well. Assuming a house of moderate size, though, greedy-search or even breadth-first search would work fine. The articles on pathfinding in the "Articles" section should help you out here.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
sneftel is pointing you in the right direction. however, to expand on what he is suggesting:

essentially the structure of the room-to-room connections in your house form a directed graph, with each room being a node, and each doorway being an edge between two nodes. basically, once you have formed this graph, you run a search algorithm on the graph, given the start node and the goal node. since it sounds like you are interested in a "quick-and-easy" approach and since you probably have not encoded any distance information into your room data structures (which is necessary for forming a heuristic estimate in an A* search), i would suggest breadth-first search.

just curious...what is this for?

-------------------------------------------------------
A headache, ancillary; an hourglass auxiliary.

"something witty, blah, blah, blah"
--That One Witty Guy (remember? that one dude?)

(author of DustBot)

Share this post


Link to post
Share on other sites
Yes, the NPC knows which room to go to.

Thank you for the replies. After looking at the suggestions I see what you''re talking about. I''m creating a text adventure.

Share this post


Link to post
Share on other sites