Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[vitaoma]

I just can't make my own algorithm, I can't even get this to work

Code: [Select]

. . . . .
. ^ O . .
. ^ . . .
. ^ . . .
X ^ . . .

Where X is the "hero", ^ is a mountain where the hero shouldn't be able to walk and O is the final objective.
I have been trying for like two weeks now, I have already checked some sites on it etc etc... but I don't want to have anything copied, I wanna understand it and do myself.
The guy always gets stuck behind the mountain =P.

[Calculus]

Post your code, mate!

[vitaoma]

I usually end messing up all the stuff, so I will tell you how I am doing. It's not a compiler error.
Consider the following:

hero[0] -> hero X position
hero[1] -> hero Y position

targetX -> target X position
targetY -> target Y position

If hero[0] is greater than targetX, hero[0]+1 exists and the tile is not a mountain, hero moves a square in the X axis.
If hero[0] is lesser than targetX, hero[0]-1 exists and the tile is not a mountain, hero goes back a square in the X axis.

Same thing in Y axis and I don't know how to make it any further. Any help is appreciated. Thanks.

[Virex]

The problem with your aproach is the part where you handle the unpassable tiles. At least the way you explained it, it seems like you're just putting the character back on it's previous position whenever he can't cross the next tile. But since you don't chance anything else, he'll just try to pass the same tile again and get set back again. Thus you're not getting anywhere soon.

If your maps are quite simple, and by the looks of it they are, then the simplest solution would be to use a dumb aglorithm. Just send out virtual to the adjacent tiles, and store the direction each of them has gone. Then repeat that. Eventualy, one of the virtual characters will reach the objective. Just extract the path data from that virtual character and pass it to the real character, and watch in awe as he travles along the fastest path possible

Note that such an aglorithm is horribly unoptimised, so I would not recommend it if you intend to have a lot of characters using the same aglorithm. However, if you'd cull pathfinding to only those on screen and keep the amount of characters on screen low you should be fine.

[vitaoma]

That might work but I'd like a better one because I will have more characters but the map should stay simple (made of passable and impassable tiles only).

[Virex]

I looked around a bit, and it seems like this is the aglorythm that is described by the roguebasin wiki here and here. I'd say it'd be a decent place to start.

If you however find that such an aglorithm is still to slow, which is unlikely unless you're doing LotR scale battles, you might want to lok into the A* aglorithm (http://en.wikipedia.org/wiki/A*_search_algorithm)

[qwertyuiopas]

There is also simple wall following.
You might want a function that returns if a character can move without actually moving them.

[vitaoma]

Thank you very much guys, I actually looked in the A* algorithm while searching for the algorithm but the other ones seem very helpful, thanks.