AI Pathfinding for text adventure
Author
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?
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
"Sneftel is correct, if rather vulgar." --Flarelocke
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)
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)
Author
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.
Thank you for the replies. After looking at the suggestions I see what you''re talking about. I''m creating a text adventure.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
