Turing Auto Walk Sprite HELP!?!?!?

[Shockdot]

I need somone to tell me how to make a Sprite Auto Move by itself...
Also make so it stops if it hits red areas
Like PacMan Ghosts...
Need this fast thanks.

[Euphoracle]

Draw it X many pixels away from where it was last frame, and when it hits a wall, change direction. You're asking too broad a question.

[Shockdot]

ok..
I am trying to make it so that a Ghost chases Pacman around the screen, but if it hits walls (that are red) it finds a way around them.

Like any PacMan game the ghost is supposed to try to catch Pacman. I have the User moving PacMan but i need the Ghosts to move around at random WITHOUT anyone having to control them.

My problem is i can not find a way to make it so the Ghost follows PacMan without going through a wall....

HOW DO I MAKE GHOST FOLLOW PACMAN AHHHH I AM GONNA BLOW UP!!!! zz

[Euphoracle]

One method is through pathfinding. Given a grid,

code:

1  2  3  4 1 [G][X][ ][P] 2 [ ][X][X][ ] 3 [ ][ ][X][ ] 4 [X][ ][ ][ ]

Where G is your ghost, and P is pacman, you can use the squares adjacent to you to perform a graph search to find the quickest route to pacman.

Given that G starts on (1,1) and P starts on (4,1), you can determine which squares are adjacent to G to find a route to P. The squares adjacent to G are (2,1) and (1,2). From the diagram, you can see that (2,1) is inaccessible, sot hey can be ignored.

We're not at pacman, but we're making our way. Continuing this method, we move to (1,3) since (2,2) is inaccessible. We repeat this process until we reach pacman.

This example has been very simple, because I have set it up in a way that there is only 1 possible path to pacman. This was to demonstrate how to use adjacencies.

Given this new grid,

code:

1  2  3  4  5  6  7 1 [G][X][ ][X][ ][ ][ ] 2 [ ][ ][ ][ ][ ][ ][X] 3 [ ][ ][ ][X][X][ ][ ] 4 [X][X][ ][X][X][ ][ ] 5 [ ][X][ ][ ][P][ ][ ] 6 [ ][X][X][ ][X][X][ ] 7 [ ][ ][ ][ ][ ][ ][ ]

Now you can see that, since there are multiple adjacent paths, it will be very difficult to use the simple method outlined above. One approach for this new problem is to use the breadth-first graph search (http://en.wikipedia.org/wiki/Breadth-first_search).

Given that G starts at (1,1) and P starts at (5,5), you can use adjacent squares in a different way to determine the shortest path to pacman. The breadth-first search works in a way such that you check each adjacent square from your initial position, and continue checking adjacencies of each of those positions, and so on, until you reach pacman. This method will always find the shortest path first, because of the way it is performed.



This can be done using a FIFO collection type, and queuing up positions, while keeping track of the path taken through metadata of some sort. The Record structure in turing is perfect for this, however, you will have to play around with flexible arrays to make it work nicely as a FIFO collection.

Ok, so! By queuing adjacent squares, setting them as VISITED, so you don't revisit them on another path, and keeping track of the entire trail from which you started, you will eventually end up with a set of coordinated of which to follow.

First, you will explore (1,2), as it is the only option. Then you will explore both (1,3) and (2,2), and from there, (2,3) will be explored, as will (3,2). Note: It doesn't matter which square explores (2,3), as the distance to each of these squares is the same.

Here, however, is where the magic happens. (2,3) will explore (3,3), and from there will go downwards (given the nature of the algorithm) and will find P after going right. (3,2), however, will go left, then down, the right again, reaching P in 10 moves. The path from (3,3) will take 8 moves.

The shortest path using this method will resolve to:

(1,1) @G
(1,2)
(2,2) OR (1,3)
(2,3)
(3,3)
(3,4)
(3,5)
(4,5)
(5,5) @P

code:

1  2  3  4  5  6  7 1 [G][X][ ][X][ ][ ][ ] 2 [G][g][ ][ ][ ][ ][X] 3 [g][G][G][X][X][ ][ ] 4 [X][X][G][X][X][ ][ ] 5 [ ][X][G][G][P][ ][ ] 6 [ ][X][X][ ][X][X][ ] 7 [ ][ ][ ][ ][ ][ ][ ]

If pacman will be moving, this search can be performed multiple times, or you can find a search that fits your needs. Perhaps A* will perform better, given the need for the fastest calculation for the shortest path? You decide! (http://en.wikipedia.org/wiki/Category:Graph_algorithms) (http://en.wikipedia.org/wiki/A*_search_algorithm)

[andrew.]

This is kind of off-topic from the original post, but Euphoracle, what would happen if the path was blocked? Would the computer keep trying to find a path or would it realize that it is blocked? You would have to program some way to tell if it is blocked or not.

[Euphoracle]

andrew. @ Sun Jan 04, 2009 11:44 am wrote:

This is kind of off-topic from the original post, but Euphoracle, what would happen if the path was blocked? Would the computer keep trying to find a path or would it realize that it is blocked? You would have to program some way to tell if it is blocked or not.

When you've run out of adjacent squares to queue, I guess you won't be able to return a path. The algorithm will stop, because it won't re-explore paths. It only explores non-visited adjacent locations. When those run out, it will stop working on that path, or the entire problem if there is no possible path. You'll have to properly handle such a situation, but I doubt that will be the case in pacman, as there should always be a route