Vadi wrote:
One thing that needs to be decided first is the map storage model... so it can work both on muds where you have an exit in every direction and the limited once.
Yeah, I think finding a balance between optimizing it for limited-exit-muds and all-exits-muds may be a challenge, especially when it comes to pathfinding. Limited-exit-muds have the advantage of, well, fewer exits, so there are fewer paths you have to consider. All-exit-muds, usually have the advantage of having geographically very "logical" connections, which allows you to estimate distances between rooms for pathfinding (particularly, when the rooms follow a strict coordinate system). So in the latter kind, some heuristic pathfinding algorithms may be advantageous, whereas in a mud with few exits (and optimally few rooms), a "just compare every possible path" approach may work fine. We'll probably have to find something in between there.
But unless the plan is to implement two different storage models, one for limited-exit-muds and one for the others (which
may be an efficient, but also cumbersome approach), I guess it should be based on the model of limited exits, since that's the more general case. (Since muds of the other kind also have a finite number of exits, just a larger one.)
A storage model somewhat similar to IMaps may therefore still be the best option. (I.e. store a unique room id, a room name, all exits along with the room ids they lead to, and possibly further information). Personally, I'd love it if the kind of further information you wish to store was customizable, to some degree. I.e., some muds may have the concept of "areas" or "environments", whereas others have entirely different room properties.
One question is also whether it might be worth it storing some data several times, in slightly different forms, to increase processing time. For instance, a room might be stored somewhat like this:
Code: Select all
roomlist = {
{
name="Someroom",
connects={{id=15,dir="east"},{id=252,dir="southeast"},{id=352,dir="south"}},
exits={east=15, southeast=252, south=352},
--further room properties
}
}
Here, the information of which exits exist and where they lead are actually stored thrice. Once, as a list "connects", which would probably be the most useful format for pathfinding routines. Once as a dictionary, where you can look up where each exit leads to (useful for tracking manual movement, etc.).
Of course, it would work just as well with just a single one of these subtables and it would save storage space (plus slightly increase mapping time), but processing the map after it has been mapped would in turn be faster and simpler, since it saves you to loop through tables to find certain values, in contrast to just directly indexing them.
Also, an algorithm for pathing.
Here again, one question is probably whether we can take into account heuristic guesses (such as the remaining distance from a certain room to the desired end room), or whether that's not possible. Also: Whether it's absolutely required to find the shortest path, or just a relatively short path, respectively: How much processing time we're willing to offer in favour of a shorter path.
If it's just about finding -any- path, the task is rather easy. I came up with a little crude lua demo for something like that:
Code: Select all
function resetRoomlist()
roomlist = {
{connections={2,3,4}, parent=nil},
{connections={1,3}, parent=nil},
{connections={1,2,5,6}, parent=nil},
{connections={1,5,7,8}, parent=nil},
{connections={3,4}, parent=nil},
{connections={3,7,8,9,10}, parent=nil},
{connections={4,6,10}, parent=nil},
{connections={4,6,11}, parent=nil},
{connections={6}, parent=nil},
{connections={6,7,12}, parent=nil},
{connections={8,13}, parent=nil},
{connections={10}, parent=nil},
{connections={11,14,15,16,17}, parent=nil},
{connections={13,15,16,17}, parent=nil},
{connections={13,14}, parent=nil},
{connections={13,14,17}, parent=nil},
{connections={13,14,16,18,19}, parent=nil},
{connections={17,19}, parent=nil},
{connections={17,18,20}, parent=nil},
{connections={19}, parent=nil}
}
end
function findPath(startnode, endnode)
local closedlist = {startnode}
local openlist = {}
local currentnode
local revpath = {}
local path = {}
resetRoomlist()
roomlist[startnode]["parent"] = 0
while(not roomlist[endnode]["parent"]) do
currentnode=closedlist[#closedlist]
for i, node in ipairs(roomlist[currentnode]["connections"]) do
if not roomlist[node]["parent"] then
openlist[#openlist+1] = node
roomlist[node]["parent"]=currentnode
end
end
if #openlist > 0 then
closedlist[#closedlist+1]=openlist[1]
table.remove(openlist,1)
else
return false --no path found
end
end
revpath[#revpath+1]=endnode
while(roomlist[revpath[#revpath]]["parent"] ~= 0) do --tracing back
revpath[#revpath+1]=roomlist[revpath[#revpath]]["parent"]
end
for i = #revpath,1,-1 do --reverse the path
path[#path+1]=revpath[i]
end
return path
end
(I'm totally inexperienced with pathfinding stuff, so excuse the primitive approach here.)
Example: findPath(6,17) returns the following path between room 6 and room 17: {6, 8, 11, 13, 17}
This does something like a "spiral search" around the starting room; i.e. it adds all adjacent rooms to a list, then it adds the rooms adjacent to
those rooms to the list, and so on, until it hits the target room. Then it traces back the path according to which rooms were called from which other rooms.
I
think this will always find the shortest path (as long as there are no differing "costs"/durations by taking different exits), but it won't be very efficient on huge numbers of rooms. It would have to be optimized a lot for that, by adding heuristic guesses.
P.S. I did some testing with randomly generated "worlds" consisting of up to a million rooms, with 2-8 exits each and some rather large distances between starting and ending rooms (up to several thousand steps), and the algorithm posted above performed surprisingly well. I can't really say if it actually
did find the shortest possible path in all cases (but it may very well have), but it always found one within a few milliseconds. (With three or four exceptions that took a bit longer than a second to calculate - but very often it took less than 10 milliseconds.) Of course that may have to do with the way I generated the room list - it may be somewhat different with room lists from an actual mud, I don't know. I'd have to get hold of a large map of a mud to test this with.