Implenting a pathfinding system.

[Spearor]

I'm implenting an breadt first search method for calculating unit movement. It working alright but the problem is that i can modify it to just show the tiles i can move to instead of finding the fastest path.
I removed

Code:

'Are we at the end?
  IF CurX% = EndX% AND CurY% = EndY% THEN EXIT DO

with

Code:

b=2*unitMP(0)*((unitMP(0))-1)

if a = b THEN EXIT DO
a = a + 1

which just keeps a hold of the search cycles, but it doesn't work properly when there are obstacles, only without.
With this modification the possible to move to tiles shift up to the right when there are obstacles in the left.

Well to make it more clear:

PS: in this test program, unitmp%(0) = 5, the movement points the imaginary unit got)

Code:

sub pathfind
    
DIM X%(40 * 40), Y%(40 * 40)
DIM Parent%(40, 40)

StrX% = 10
StrY% = 8
EndX% = 7
EndY% = 3

QP% = 0
QL% = 0

QL% = QL% + 1
X%(QL%) = StrX%: Y%(QL%) = StrY%
Parent%(StrX%, StrY%) = -1
a = 0  
b=2*unitMP(0)*((unitMP(0))-1)

DO WHILE QP% < QL%


'Temporary reference current position
  QP% = QP% + 1
  CurX% = X%(QP%): CurY% = Y%(QP%)

  'Are we at the end?
  'IF CurX% = EndX% AND CurY% = EndY% THEN EXIT DO

'Try going right

  IF Mapd(CurX% + 1, CurY%) AND Parent%(CurX% + 1, CurY%) = 0 THEN
    QL% = QL% + 1
    X%(QL%) = CurX% + 1: Y%(QL%) = CurY%
    Parent%(CurX% + 1, CurY%) = 1
    possiblemove(curx%+1,cury%) = 1  
  END IF


  'Try going left

  IF Mapd(CurX% - 1, CurY%) AND Parent%(CurX% - 1, CurY%) = 0 THEN
    QL% = QL% + 1
    X%(QL%) = CurX% - 1: Y%(QL%) = CurY%
    Parent%(CurX% - 1, CurY%) = 2
    possiblemove(curx%-1,cury%) = 1
  END IF

  'Try going down

    IF Mapd(CurX%, CurY% + 1) AND Parent%(CurX%, CurY% + 1) = 0 THEN
    QL% = QL% + 1
    X%(QL%) = CurX%: Y%(QL%) = CurY% + 1
    Parent%(CurX%, CurY% + 1) = 3
    possiblemove(curx%,cury%+1) = 1
    END IF


'Try going up

    IF Mapd(CurX%, CurY% - 1) AND Parent%(CurX%, CurY% - 1) = 0 THEN
    QL% = QL% + 1
    X%(QL%) = CurX%: Y%(QL%) = CurY% - 1
    Parent%(CurX%, CurY% - 1) = 4
    possiblemove(curx%,cury%-1) = 1
    END IF


if a = b THEN EXIT DO
a = a + 1

loop

My testprogram, just insert some bluetinted tiles (obstacles) in the map, then the pathfinding stops working correct. (you can change the obstacle lvl of the tiles at the right with 0 or 1)

http://s33.yousendit.com/d.aspx?id=08370...MOKZZT5RQC


The tutorial i got it from:

http://www.petesqbsite.com/sections/expr...athfinding

[mjs]

Search for A* or Dijkstra's algorithm.

Regards,
Mark

[Spearor]

Search for A* or Dijkstra's algorithm.

Regards,
Mark

well thnx, but you could understand i already did that.
The BFS method is the easiest and fastest way for implenting this kind of system.

[mjs]

BFS is very expensive regarding memory and execution time compared to Dijkstras algorithm. Please read the description here: http://ciips.ee.uwa.edu.au/~morris/Year2...kstra.html.

Regards,
Mark

[Spearor]

BFS is very expensive regarding memory and execution time compared to Dijkstras algorithm. Please read the description here: http://ciips.ee.uwa.edu.au/~morris/Year2...kstra.html.

Regards,
Mark

Well i have no problem finding the shortest path. I could implement the A* algo, what i'm gonna do soon, but then i still don't know how to adjust it that it shows all the possible to move to tiles with an specified movingpoints instead of calculating the shortest path.

[mjs]

Sorry, but I simply didn't / don't understand what you problem is ... do you want to know how to find out all possible ways to a different tile?

Regards,
Mark

[Z!re]

Spearor, the most efficient would probably be a square search (assuming you can move diagonally)
Then do A* or, whatever you prefer, from that tile, to the "center" (or the other way around)

Flag all tiles in the path as "ok", otherwise flag the tile as blocked..

Move to next, if it's not already flagged, repeat the above..

[TheBlueKeyboard]

I agree with everyone here, A* is probably best.

[Torahteen]

Please elaborate your predicament in english.

Edit: If A* is all you're having trouble with, look at my tutorials in QB Express Issues 13 and 14.