Path Finding through a random arrangement

[Nisheeth]

As I specified in my previous post, I was making the Dungeon Crawl Game that has been listed in the Beginner Exercises in this site.
My Idea is to create an Enemy that will try to come towards the Player, and another that will go towards the treasure. But for that I wanted to know how do I make a Path Finding Algorithm.
The treasure will be on a constant place, while the Player will move.

This is the link to my code so far:
http://pastebin.com/NkB4tiki

I would also be placing the traps, so I would like to know how to have the program understand that it should not step on the traps.

Could someone help me on how to do this?

[hamsterman]

Red up on "A star" pathfinding algorithm. There should be plenty of tutorials on the internet.

[Nisheeth]

Looked it up. Found a couple of tutorials, but most of them were a bit too hard to understand, or implement. The other two problems I was having were:
1. The algorithm includes Diagonal moves as well. I wanted only the four main directions to be included in the search.
2. One of the targets will be moving, I can't think of how this process can work effectively in that case.

Any help??

[hamsterman]

It's true that A* is a bit tricky.
1. A* itself does not restrict you to any number of directions, you get to choose that.
2. This does complicate things. I'm sure there is a way to optimize the process, but I don't know what it is. Though A* isn't as computationally expensive as it may seem.

How random is your map going to be? A* can find the shortest path in any maze, however if your map is going to be simple, you could use a simpler algorithm. Basically "turn when you hit a wall. if possible turn towards the target." Something like this would have many problems with a pocket in a wall. Smarter algorithms of similar nature can be figured. Not as smart as A*, but possibly sufficient. For example consider PacMan. Ghosts use very simple logic, but perform well in the simple map. To write such good pathfinding you need to have an idea of how your map is going to look.

[Nisheeth]

How random is your map going to be?

Completely random! as You can see through the code, any block can be a trap, and a number of times it may even be unsolvable!

Could you tell me how to make the character understand that it has to move towards the target?
And the movement of one target will be the player.

[hamsterman]

The code you posted doesn't seem to have any randomization in it.. But that's not the point. I meant to ask about features of the map such as density of walls/traps. If you're just doing map[rand]=wall in a loop, I suppose there aren't any other features to consider.

I only meant things like

if( target_x > x ) x++;
else if( target_x < x ) x--;
else if( target_y > y ) y++;
else if( target_y < y ) y--;

plus checking that map[new_x][new_y] is not a wall. Of course this would get stuck behind almost anything. The one I suggested might perform a bit better but it's still terrible. If you try out several variants, look at where they fail and try to solve those problems, you might come up with something satisfactory.

Are you sure you don't want to try A* ?

[Nisheeth]

The code you posted doesn't seem to have any randomization in it.

Sorry, forgot to update it again after I included the traps! Done so now.

Are you sure you don't want to try A*

Main problem with using it is that I didn't understand it.