I've looked at A*, but can't figure it out. Ereon said he'd get back to me, but its turning a bit slow, so I'm thinking of seeing which one of you is faster. I understand BM far better than any other language, but Pseudo, or BB is better than nothing.

------------------
MM out-
Thought travels much faster than sound, it is better to think something twice, and say it once, than to think something once, and have to say it twice.
"Frogs and Fauns! The tournament!" - Professor Winneynoodle/HanClinto
I reserve the full right to change my views/theories at any time.

It's written in BASIC, so you would need to convert it to whatever you are coding in, but it shouldn't be impossible.

Also, are you using a tile engine for movement of characters? Or a tile engine to create the background graphics and the characters can move wherever they want. I suspect that the characters move tilespace by tilespace, right.

And one last thing, can the characters move diagonally?

------------------
Visit my portfolio (and check out my projects):
www.JestermaxStudios.com

you could google for it too

------------------
John 14:6

Jesus answered, "I am the way and the truth and the life. No one comes to the Father except through me.

------------------
Visit my portfolio (and check out my projects):
www.JestermaxStudios.com

If can understand and implement it, you're a coder.
It'd be worth it for you to start a project JUST so you can use it.

------------------
Q.E.D.

Arch/Everybody else.

I'll look into that algorithm.

------------------
MM out-
Thought travels much faster than sound, it is better to think something twice, and say it once, than to think something once, and have to say it twice.
"Frogs and Fauns! The tournament!" - Professor Winneynoodle/HanClinto
I reserve the full right to change my views/theories at any time.

quote:

---

Originally posted by jestermax:
Try reading some theory on Dijkstra's Shortest path algorithm. they're very similar but i think Dijkstra's is a but more basic and easy to implement iteratively.

---

I think its also a lot slower since it doesn't have the heuristic element and has to search *every* direction.

It seems like Mene has equally weighted paths (40 pixel segments) and since the vision system or distance to destination could add the heuristic element, I personally think that A* is a better choice.

I've stubbed out a section on the wiki for Game Algorithms on the Game Design page. Perhaps we all flesh out that section as we have time.

God Bless!

------------------
Sam Washburn

Check out my CCN SpeedGame 2 Blog

------------------
Psa 32:5 I acknowledged my sin unto thee, and mine iniquity have I not hid. I said, I will confess my transgressions unto the LORD; and thou forgavest the iniquity of my sin. Selah.

[VoHW] (Help needed) [Blog] (Contact) - Truedisciple (mp3)

quote:

---

Originally posted by Mene-Mene:

I've looked at A*, but can't figure it out. Ereon said he'd get back to me, but its turning a bit slow, so I'm thinking of seeing which one of you is faster. I understand BM far better than any other language, but Pseudo, or BB is better than nothing.

---

I learnt A* from this website: Amit's Game Programming. You could see if that helps you understand it.

------------------
http://www.geero.net/

------------------
MM out-
Thought travels much faster than sound, it is better to think something twice, and say it once, than to think something once, and have to say it twice.
"Frogs and Fauns! The tournament!" - Professor Winneynoodle/HanClinto
I reserve the full right to change my views/theories at any time.

You might want to try this: get a piece of graph paper. choose a starting point and ending point and draw some obstacles on it. Make sure that you stay on the lines of the graph paper.

Then, pretend you are a computer trying to get from start to finish. Put a "1" on the squares around the starting place. That means, if you took one step, then those are all the possible places you would be. If your character can't move diagonally, then don't put 1's in the diagonals.

Next put a "2" around all the 1's. But if there's a number already there then don't put a number there. If there is an obstacle, don't put any numbers there, either.

Eventually you'll get to your ending point. Now get a red pen or something and draw boxes around the numbers as they descend. Start at the end and draw a box around the lowest number that's next to it. Pretend it's the number 17. There will always be a 16 next to the 17 so draw a box around the 16. Then 15, etc. until you get to 1. There's your path.

I'll post some pictures and code on the wiki later.

http://googleblog.blogspot.com/2007/11/road-to-better-path-finding.html

------------------
John 14:6

Jesus answered, "I am the way and the truth and the life. No one comes to the Father except through me.

I think the strangest part was constructing an efficient priority queue--sort of the key to A*. I actually did a linear search when inserting elements, but I start at the point of last insertion, which is generally "close" to the correct location.

Here is the wikipedia psuedocode.

function A*(start,goal) var closed := ''the empty set'' var q := make_queue(path(start)) while q ''is not empty'' var p := remove_first(q) var x := ''the last node of p'' if x in closed continue if x = goal return p ''add x to closed'' foreach y in successors(x) enqueue(q, p, y) return failure

------------------
+---------+
|steveth45|
+---------+

------------------
MM out-
Thought travels much faster than sound, it is better to think something twice, and say it once, than to think something once, and have to say it twice.
"Frogs and Fauns! The tournament!" - Professor Winneynoodle/HanClinto
I reserve the full right to change my views/theories at any time.

Draw circles around the target - when you find the source move in circle by circle.

Hope this helps you get a grasp on it. It always helps me to visualize it.

In pic 1, draw your start and finish (source and target)
In pic 2, then draw a maze, or some obstacles.
in pic 3, be the computer. Put a 1 around your starting point. This corresponds to 1 step by NPC
in pic 4 and 5, put a 2 around each 1.
in pic 6, they are concentric circles. Diamonds, really, because we are limiting motion to NSEW

pic 7 - the 12th step for the NPC. The paths are starting to close in on themselves in places.
pic 8 - the 20th step lands on the target
pic 9 - work it backwards, 19, 18, 17
pic 10 - there's your shortest path
pic 11, 12 - a more complex maze

I'd suggest doing a few of these to understand basic pathfinding. I'll see if I can dig up my code...

[This message has been edited by JeTSpice (edited November 19, 2007).]

[This message has been edited by JeTSpice (edited November 19, 2007).]

------------------
Sam Washburn

Check out my CCN SpeedGame 2 Blog

------------------
http://www.geero.net/

[This message has been edited by andygeers (edited November 20, 2007).]

In my game, I'm using pathfinding as a way to navigate a very complex maze of trees. The dense forest is created randomly, so I'm using the process above.

Another thing to consider is the size of the map. In my game, it's 32 x 24. When a player directs a PC or an NPC has to navigate, the distance is very small, ususally within 10 tile spaces (or about 400 pixels). I think the most steps I've seen an NPC have to take is about 40. So this simple pathfinding approach works well for the needs of my game.

But if you are working with a scrolling map, the pathfinding technique I've laid out is definitely going to slow you down. In such a case, you can limit the computer's search to a "bird's eye view" from start to finish, as Steveth45 says.

If you are not working in maze-like terrain, but simply need to navigate around a few buildings or trees or something, you can do this:

Draw a straight line from NPC to target.
Check for collision along that line.
If you get a collision, then find the farthest point from the line in within the collision footprint. Call that point A.
Erase the first line and draw two lines, one from NPC to A, and one from A to target.
Repeat until no collision.

This technique will not always give you the shortest distance, but it will give you a natural feel of the way that real people find their destination: They walk toward it, avoiding obstacles.

Okay, I won't post my code, because it's long and might not be helpful anyway. But if you need any other help or explanation, I'm here.

------------------
MM out-
Thought travels much faster than sound, it is better to think something twice, and say it once, than to think something once, and have to say it twice.
"Frogs and Fauns! The tournament!" - Professor Winneynoodle/HanClinto
I reserve the full right to change my views/theories at any time.

[This message has been edited by Mene-Mene (edited November 20, 2007).]

------------------
MM out-
Thought travels much faster than sound, it is better to think something twice, and say it once, than to think something once, and have to say it twice.
"Frogs and Fauns! The tournament!" - Professor Winneynoodle/HanClinto
I reserve the full right to change my views/theories at any time.

http://www.christiancoders.com/cgi-bin/code/code_showentry.pl?id=mene-mene11282007111103&comments=no

------------------
MM out-
Thought travels much faster than sound, it is better to think something twice, and say it once, than to think something once, and have to say it twice.
"Frogs and Fauns! The tournament!" - Professor Winneynoodle/HanClinto
I reserve the full right to change my views/theories at any time.

It is an array, the exact size of the map, which contains all the spaces that cannot be walked on. In your WoB screenshot, it would be all the squares where the yellow walls are.

Here's the line:
if doodad_map(x,y) = 0 and trigger_map(x,y) = 0 and path_map(x,y) = 0 and end_flag = 0 then...

This line checks various maps to make sure that the space is walkable.

( doodad_map actually tells the computer where to put houses, trees, and other props. I used this because the props are irregularly shaped (don't fit into tiles) and so I needed two map arrays -- one for terrain, and one for objects.)

( trigger_map is kind of the same thing - mostly it's used for water and lava which are terrains that the NPCs should avoid (no pathfinding). But I wanted the player to be able to accidentally move the character into the lava.)

You probably don't want to use the exact words "doodad_map" and "trigger_map."

You can shorten that line to:
If path_map(x,y) = 0 and end_flag = 0 then...

And then add other conditionals (within that same line) which tell the pathfinding routine to avoid the yellow walls. The conditional needs an array with the same dimensions as your map. You might already have such an array in the program?

if path_map(x,y) = 0 and end_flag = 0 and (there's no yellow wall on space x,y) then...

- evaluate the distance between [grid positions at current level (1,2,3,n)] vs [goal position]
- whichever [grid positions at current level] still has the "shortest distance" to [goal position] is the way to go
- if they are equal, explore all "shortest distance" options available
- disregard it if the next [grid positions at current level] fails the "shortest distance" test

[This message has been edited by mastallama (edited November 28, 2007).]

Steveth45 talked about line-of-site being the best option, and AndyGeers pointed out why the approach I outlined is not as efficient.

I'd guess you're right, MastaLlama, but I'd like to hear from somebody who knows. (And if they could baby-step us, cool. (Because there A* tutorials out there are ???confusing??? to me.)

[O][O][O][O] [O] [S] [O] [E] [O] [O][O][O][O]

Then my additions would cause the computer to go right first, then around the [O]bstacles because the [E]nd point is closer ...instead of to the left first to get around the [O]bstacles.

Cool idea, MastaLlama.

So, the path would go toward the right, and hit the wall and randomly turn up or down and then turn again, making a u-turn. But the code would be checking each new step for direct paths to any previous step, and the u-turn would be omitted.

It would kind of be like taking out the slack in the path.

Another intersting one is bi-directional search where you search from both the start point and end point and actually calculate smaller paths by retargeting your searches for the new start point and new end point.

[O][O][O][O] [O] [S] [O] [E] [O] [O][O][O]

compare [S] to [E]

from [S] go to [1]
from [E] go to [a]
compare [1] to [a]

[O][O][O][O] [O] [S][1] [O][a][E] [O] [O][O][O]

from [1] (instead of [S]) go to [2]
from [a] (instead of [E]) go to [b]
compare [2] to [b]

[O][O][O][O] [O] [S][1][2][O][a][E] [O] [b] [O][O][O]

from [2] go to [3]
from [b] go to [c]
compare [3] to [c]

[O][O][O][O] [O] [S][1][2][O][a][E] [O][3][c][b] [O][O][O]

This would work faster than concentric circles because it pulls you towards where you need to go instead of checking every possibility.

For bigger maps it would work the fastest to get A* under your belt. I don't understand how it works just yet, but I'm getting closer

[This message has been edited by mastallama (edited November 28, 2007).]

------------------
MM out-
Thought travels much faster than sound, it is better to think something twice, and say it once, than to think something once, and have to say it twice.
"Frogs and Fauns! The tournament!" - Professor Winneynoodle/HanClinto
I reserve the full right to change my views/theories at any time.

1.) in WoB, you need the NPC to move only if he sees the player or

2.) in MastaLlama's example, the NPC will only move if he sees the player.

?

Mene-Mene, I did a tech demo once similar to the movement you are talking about. If I have time tonight, I'll try and dig it up and let you take a look at my code (it's in Blitz3D but it's 2d interaction and code).

It seems like the hard part for you will be getting the enemy to *not* go after the player when the player is not in the enemy's field of view (FOV). I think Ereon (?) was doing something with FOV before where I made the following images as examples:

It shouldn't matter that the enemy has to see the player before he will move. You would simply not call the pathfinding subroutine unless the enemy sees the player. The "enemy seeing the player" would be one of the conditions which needs to be satisfied before pathfinding is called.

However, do you need pathfinding at all? If the enemy will only move when he sees the player, then that is a straight line between player and enemy: in this case, no pathfinding is needed. Just do something like this:

If enemyX < playerX then enemyX = enemyX + 1
if enemyX > playerX then enemyX = enemyX - 1
if enemyY < playerY then enemyY = enemyY + 1
if enemyY > playerY then enemyY = enemyY - 1

Maybe you want to ensure that if the player ducks behind a wall, the enemy won't just stand there, not knowing what to do, but will walk around the wall. Is this true? Then you will need pathfinding.

Mastallama: It was penny, and the code I have so far is http://www.christiancoders.com/cgi-bin/code/code_listentries.pl?id=AL (Or just look under algorithms in the code place here. It doesn't account for obstacles yet.

JeTSpice, yeah, that i suppose would work, as there can't be any obstacles there anyway... lol. a small oversight and overcomplication...

------------------
MM out-
Thought travels much faster than sound, it is better to think something twice, and say it once, than to think something once, and have to say it twice.
"Frogs and Fauns! The tournament!" - Professor Winneynoodle/HanClinto
I reserve the full right to change my views/theories at any time.

quote:

---

Originally posted by mastallama:
So, to take JeTSpice's example and turn it into A*, would I be correct in stating the following? ...or does it just turn it into Best-First-Search?

- evaluate the distance between [grid positions at current level (1,2,3,n)] vs [goal position]
- whichever [grid positions at current level] still has the "shortest distance" to [goal position] is the way to go
- if they are equal, explore all "shortest distance" options available
- disregard it if the next [grid positions at current level] fails the "shortest distance" test

[This message has been edited by mastallama (edited November 28, 2007).]

---

The pseudo-code here is fairly easy to follow on how A* works.

Each square has three values:
g: the cost of reaching this square from the starting point
h: the heuristic of how far it is from here to the destination point (a good start for h is the number of moves it would take if there were no obstacles to avoid)
f: the sum of these (g + h)

You then keep two lists: OPEN (a list of squares that we're going to evaluate) and CLOSED (a list of the squares that we've already evaluated). You seed OPEN with the starting square, and CLOSED starts off empty. As you examine each square in OPEN, you add all of its neighbours to OPEN (at least, the ones that aren't already in CLOSED) and then add the square itself to CLOSED.

The magic is the data structure you use for the OPEN list: rather than being a straight forward queue or stack kind of thing, you use what's known as a 'Priority Queue' - each item in the list has a rank associated with it (in this case, f) and each iteration we start by examining the LOWEST ranking square in OPEN. Since f is sum of g and h (i.e. the cost to get TO that square plus the rough cost to get FROM that square) then the square with the lowest f is theoretically the square that's easiest to get to and closest to your destination, i.e. well worth evaluating.

And very very roughly, that's A*

------------------
http://www.geero.net/