Re: Maze routing (was '"Smart" movement')

[Erik Jessen <erik dot jessen at home dot com>]

In most games, I would imagine the number of cells to be searched would be
relatively low.
There are some pretty standard algorithms for solving that sort of
problem.  Also, I'd add
in a mode that allows people to specify preferred paths from A to B.  This
would be useful
in helping the computer in the above case, or if one wanted to avoid a
potentially hazardous area
(i.e. don't send the merchant ships on a long trip, and have them go
anywhere near land that
might be enemy occupied at some point during the trip).

One also could use waypoints, and then the large single problem is broken
down into several simple ones.

Off topic: one good thing about Windows, is that I always have a steady
set of favors to cash in on,
from all the people who I've helped to reinstall/rebuild their Windows
system.  Painting, carpentry,
clothing design, everything/everybody is grist for the Microsoft mill.  :)

Erik

Bob Carragher wrote:

> > > Is this already implemented?  Is it too much hassle, or would
> > > cause a blow-up in memory?
> >
> > It's certainly not implemented now!  It would be some work, but not
> > a ridiculous amount, and I don't think the memory consumption would
> > be huge, because the waypoints would just be tasks, and there is
> > already machinery to manage task queues effectively.  My big concern
> > would be compute time on large worlds.  Since a really twisted maze
> > route might have to wander all over the world, the algorithm to
> > compute the route might have to scan hundreds of thousands of cells,
> > so it needs to be possible to restrict the area being searched.
>
> I can imagine this concern as well.  There are ways around it.
> One is to figure out a way to restrict the search area.  A
> dialog box interface comes to mind.  Also, point-and-click
> "descriptions" of search areas might work.
>
> In any case, the user might still cause a lot of CPU time to
> be consumed.  The game could through up another dialog box which
> contains a button to stop calculations.  Then, whatever "best"
> route that was found would be displayed.  (If none were available,
> then maybe a message would be printed in the messages area stating
> that this was the case.)
>
> But these strike me as relatively easy things to do.  The harder
> task would be implementing the maze routing and the display
> aspects.  Do you agree?
>
>                                 Bob