3rd party Apps wishlist

[Tominator2]

New addition: I didnt think of it because its definetly in an area of programming I do badly at. A 3rd party program which can plot the fastest course from xxx to yyy. Read in the .map file and array the neighbor commands. Work out the shortest route.

Psuedo-code follows:

code:

---

We'll need a queue class "queue" and a list class "path".



The queue class is pretty standard.



The path class is just like a queue, except that it needs to support a "LastArea( )" method, which will return the most recently enqueued

element (addArea is just enq).  Also, it will need a contains(x) method which returns true if the path already contains x.



We'll assume that:

- areas are represented by numbers

- travel always takes one "turn"

- there is an adjacency function adj(x, y) which returns true if x is adjacent to y, and false otherwise (e.g. return map[x][y]))

- we start in area 0



path start = new path(0);

queue q = new queue;

q.enq(start);



path ans;

ans = findPath(start);



path findPath(queue q, int goalArea) {

    path curPath = q.deq( );

    int curNode = curPath.LastArea( );

    for (i = 1; i < numAreas; i++) {

        if (adj(curNode, i)) {

            if (i == goalArea) {

                return curPath;

            } else {

                if (!path.contains(i)) {

                    path tmp = new path(curPath);

                    q.enq(tmp.addArea(i));

                }

            }

        }

    }

    

    findPath(q, goalArea);

}

---

There might be a bug or two in the above code - I haven't tested it. In any case, it's a pretty straightforward breadth-first search. It's not nearly as efficient as Dijkstra's algorithm, but it is nice in that it keeps around partial paths (another function might prune a path for some game-related reason). I can't say I know anything about extracting data from .map files.

An addition would be to add terrain and have it avoid either land or water.

A simple change to the adj function.

Or even figure in terrain factors such as flyers and forest-moving units

Now it starts getting complicated, and you'll probably want an A* algorithm. I can do that, if you want to go that way.

[ March 09, 2004, 02:18: Message edited by: Tominator2 ]