Re: A85: Re: LaserSquad-Z


[Prev][Next][Index][Thread]

Re: A85: Re: LaserSquad-Z




Yeah, I saw that A* algorithm, too, but it looked to complicated to fit
on a calculator.  You might could use a simplified version of it and
create kind of a road map for the map.  You create an overlay (or use
the extra bits) to make a hidden road that connects points.  Then you
simply find the closest point, and follow the road to the closest point
to your target.  You would still have to use the other algorithm, and
homemade maps would all have to be two-player or something, but it would
work, and should be faster.  It would just look really stupid if the
unit went to the closest point if the target was right next to it, but
you could have it look for the enemy, too.  This is how I understood A*
to work..... If not I might like to use it someday, so could you explain
it any better?

Thanks,
Dave

Johannes wrote:

> Thanks! I did also find the algorithm from some
> webpages... And then I'll add that A-star thing(it
> searches the shortest points first). Now what would
> you suggest for storing the checked points? Should I
> have always growing list of all the points? It would
> end up huge I guess... any ideas? Or maybe it wouldn't
> be too big if I'd only store the furthest points of
> the search area...
>
> t333.....
> .322222..
> .321112..
> ..21s1...
> ..2111...
> .........
>
> txxx.....
> .x2xxxx..
> .xx11xx..
> ..x1sx...
> ..xxxx...
> .........
>
> x-these would be stored.
>
> Well, thanks again!
> /Johannes
>
> --- David Whittaker <tubadave@sonet.net> wrote:
> > I thought the algorithm you are using could use a
> > little optimization, so I did some research.  It
> > turns out that if you plan your path from the start
> > and finish simultaneously, you cut the number of
> > tiles you have to search in half (usually).  For
> > example:
> >
> > Your method:
> >
> > 444444444.
> > 433333334t
> > 432222234.
> > 432111234.
> > 4321s1234.      81 searches
> > 432111234.
> > 432222234.
> > 433333334.
> > 444444444.
> >
> > My method:
> >
> > ......22222
> > ......21112
> > ......21t12
> > .2222221112     50 searches.
> > .2111222222
> > .21s12.....
> > .21112.....
> > .22222.....
> >
> > Granted, there will need to be a few more searches
> > on each on to find the collision point, but you get
> > the idea.
>
> _________________________________________________________
> Do You Yahoo!?
> Get your free @yahoo.com address at http://mail.yahoo.com



References: