- I am -slowly- starting to work on a FPS game that takes place in a maze. The maze is complex rather than simple - in other words, there is [in many instances] more than one path that will allow you to reach any one point, from any other point. The game conditions will be set so that computer "enemies" may be able to spot the player and will [should] take the shortest path to find the player: the enemies are privileged in that they know the fastest path to where the player is (they are assumed to have that information from the start). What I want is a method of naming either the individual paths -or- the connecting points of paths, from which being at one path/point name and comparing to any other ''target'' path/point name, the fastest way can be found just from a comparison of the path/point names. Placing physical distance of the path (or distances between points) into the path/point names would be nice also, but I can put that elsewhere. I want to be able to scatter the enemies randomly across the maze at the start of a new game, and still have them know how to effectively pursue the player from any point. For a simple tree, there is an easy solution. The problem I have is that it will only work if there is only one way to reach any point from any other point. The "tree" diagram of the maze I need has many interconnecting paths - paths that don''t reach upwards and make their own branches, but that connect "sideways" with other branches, if you will. I can''t come up with anything that handles this real well; I''d suppose that there''s something better than trial or error. Any ideas? - Lubb

There is a simple way to apply pathfinding (thinking about your maze in 2d)..

If your bot knows the position of the player he analyses his options: if he's to his left he takes a path that leads left, if he's to his left - and below - he chooses down or left depending on which distance (x or Y) is greater. Once he's en-route he needs to make a new decision every time he reaches a junction.

This is the simplest method I know, so code it (it should only take an hour ) and see how it works.

If you want to start coding some proper AI pathfinding, only do it when you've explored the simple options.

Matt



Check out my project at: www.btinternet.com/~Matthew.Bennett

Edited by - 3dmodelman on June 12, 2000 2:53:26 PM

OK Lubb,

Upon re-reading your post I reckon my reply was a little too simplistic.

To take it a step further you need to store all the information concerning each junction, so the bot can make an informed decision.

ie. Junction no.4 has four pathways, a,b,c,d (each pathway can have it's length stored so the bot will know how long it will take him to traverse it) but each path can be stored as a start-junction and end-junction pair. You can now tell the bot which path takes hime closer to the player, by comparing the coords of the next junction (or the end of each path) to the players position.

A simple way of adding some learning ability to the bot would be to keep the knowledge of the map away from him at first. Then as he explores, you can store which pathways he knows about in his unique 'memory', so when he gets to a junction he can either choose to explore new paths or stick to the ones he knows. To stop him learning the entire map, place his memory into a buffer of say a maximum of 50 paths....

Hope this makes sense,

Matt


Edited by - 3dModelMan on June 12, 2000 3:12:19 PM

Edited by - 3dmodelman on June 12, 2000 5:36:31 PM