A85: Re: LaserSquad-Z

To: <assembly-85@lists.ticalc.org>
Subject: A85: Re: LaserSquad-Z
From: "David Whittaker" <tubadave@sonet.net>
Date: Mon, 24 May 1999 13:04:15 -0500
Delivered-To: assembly-85-outgoing@towerguard.unix.edu.sollentuna.se
Delivered-To: assembly-85@lists.ticalc.org
Reply-To: assembly-85@lists.ticalc.org

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.

-----Original Message-----
From: Johannes <porkkanamies@yahoo.com>
To: assembly-85@lists.ticalc.org <assembly-85@lists.ticalc.org>
Date: Tuesday, May 18, 1999 1:53 AM
Subject: A85: LaserSquad-Z

>
>Hello everyone, anyone!
>
>Hmmm, I wanted to write something for the list since
>it seems to have been in coma for awhile. Don't read
>this unless you have some time...heh. Maybe some of
>you have heard(well there can't be too many, I guess)
>I've been programming the good ol' _LaserSquad_ for
>TI-85. It is a turn-based combat-strategy game. Two
>players each having up to 8 crew members are fighting
>in a certain area. I've made a 35x40map for the first
>episode.(map engine handles map sizes 256x256, yeah
>too much, but there's no need to restrict that I
>suppose...) . The map engine is quite ready now
>('map-engine +menu-routines(not standard85!) +shop
>+episode1 +most of the data +80-90% of the game
>GFXs'=3.1KBs at the moment), and the menu system and
>the shop should fully work in next week. Well, some of
>you now think:"What is he talking about here?!?!" Hmm,
>I've ran into somekind of a problems(again? heh)...
>Has anyone of you ever worked with
>Pathfinding-algorithms or strategy game AIs? I've got
>a pathfinding algorithm I think I'm going to use, but
>I'd like to know if you'd have any suggestions about
>how to use the map data with it. The map looks like
>this:
>
>.db 1,0,0,0,3,27,27,27,0,...
>
>...so that each byte represents a tile #id. The tiles
>1-10 are walkable tiles. I've decided to use 32
>different tiles, so each map byte uses 5
>bits(0d-31d=0b-11111b). I thought that maybe I could
>do the pathfinding with the remaining 3 bits. But now
>I'm not sure anymore, because I'd like the enemy unit
>to not to walk in the Players Line-of-Sight area, if
>it has not enough Action Points to shoot. So I'd need
>a shadowmap of the each player units' Line-of-Sight?
>
>Ok then... Another thing is that I want to represent
>here is the Pathfinding algorithm I'm going to use
>with the game, and I'd like to hear some comments
>about it. Since I'm a mainly a graphician here's a
>visualization:
>
>..........
>.....t....
>..........
>..xxxxx...
>......x...
>..s...x...
>..........
>..........
>
>s-start
>t-target
>-------------
>
>..........
>.....t....
>..........
>..xxxxx...
>.111..x...
>.1s1..x...
>.111......
>..........
>
>I start making the way from the start...
>
>55555.....
>44445t....
>33345.....
>22fffff...
>211123f...
>21s123f5..
>21112345..
>22222345..
>
>...and when I reach the 't'-I just look smallest
>number to find my shortest route(starting from t this
>time).
>
>....p.....
>...p.t....
>..p.......
>.pxxxxx...
>..p...x...
>..s...x...
>..........
>..........
>
>I will make a routine that checks the surrounding 8
>tiles, then I use it from the start until it has
>checked it's way to the target. To speed up process
>I'll always check the distance to the 't' and check
>only the nearest tiles(if the path is not found it'll
>start checking the next nearest, and so on).
>
>Ok, this is quite basic pathfinding routine, so I know
>some of you could help me with this... luckily I have
>still 20Ks(28K-3K-Usgard=+20Ks) to fill with
>Pathfinding-, Line-of-Sight and AI-routines, hehee!
>Oh, and yes, eventhough the game looks complicated I'm
>going to release it next August(the two player version
>will be out sooner, I guess). Sorry if I bored
>anyone...
>
>/Johannes Rajala of Icarus Productions
>
>
>--
>e-Mail:
>carrot@sgic.fi
>
>Personal WWW: (not related to calcs... too much)
>http://carrot.findhere.com/
>
>IP homepage:
>http://icarus.ticalc.org/
>--
>_____________________________________________________________
>Do You Yahoo!?
>Free instant messaging and more at http://messenger.yahoo.com
>