Help on path finding
Hello everyone!
Help me please!
Have you ever played games like Baldur's gate or Diablo or classic adventure games (like Monkey island)?
What I'm saying is:
I'm trying to implement a way to move my character, on a 2D space, to the point I clicked on.
If there is no obstacle between the start and the finish points, I can make it work pretty easily (I just let the charachter walk the straight line connecting the points).
The problem is when I introduce obstacles.
I'm trying to implement the A* algorithm for the path finding process.
Since the character and the obstacles lay on a 2D plane not divided into tiles or any sort of sub-division, it is quite hard to calculate a path.
What I thought of doing is:
when I click on a destination point, I create a 2D grid surrounding the character, at its actual position, and the destination point.
The intersections between the horizontal and the vertical lines of this grid, will be the possible nodes of the path to the destination. (I hope it's clear).
The A* will calculate the best path among these nodes, considering whether a node is reachable (i.e. not overlapping an obstacle) or not.
I still haven't implemented it, so it's just an idea, and I don't even know if it works!
Is it possible there is no other way of doing that?
How do the games I mentioned above work?
My problem is finding a way to determine the possible nodes (2D points on the 2D plane) for the A* algorithm to work on.
Please help, I'm stuck.
Any suggestion?
Thank you!
P.S: If you need me to make it more clear, I'll give it a try!
[1694 byte] By [
Neo_Karla] at [2007-9-29 14:57:29]
have u had a look at the A* Thread on javagaming.org ? http://www.javagaming.org/cgi-bin/JGNetForums/YaBB.cgi?board=share;action=display;num=1037669044
Thank you for responding.
Alas, that doesn't answer my question.
That code will give you an implementation for the A* algorithm, which I can make myself.
My problem, I repeat, is determining the nodes on which the algorithm will work on.
If I used a tile system, the nodes would be the tiles themselves.
Since I'm not using tiles, I think I have to manually determine the nodes as 2D points.
Thank you anyway!
> My problem, I repeat, is determining the nodes on which the algorithm will work on.
> If I used a tile system, the nodes would be the tiles themselves.
> Since I'm not using tiles, I think I have to manually determine the nodes as 2D points.
> Thank you anyway!
Not knowing the A* algo nor having the time to look it up, I risk a random thought (sorry!), basing on your original post :
Assuming the grid is made up of regular squares, I guess that if you choose the grid's resolution (the distance between your grid's nodes) as smaller than the smallest possible obstacle, then choosing any arbitrary origin, and laying out the nodes from here, will be correct.
Now to determine the optimal grid, I have no clue.
Exactly. I'd create a, let's say, 10x10 grid or something related to the actual distance, and work on those nodes.
But, before doing that, I'd like to know how others would do that differently(sp?), especially if they knew how actual similar games work.
As alway thanks for your contribution.
>> I'd like to know how others would do that differently(sp?),
>> especially if they knew how actual similar games work.
Well, most similar games have some sort of (tile) map, and not objects freely thrown around on a 2D space. Maybe you should consider redesigning your game to take this approach, as it will make development easier (not only for path-finding, but for extra-level creation, saving memory, etc...)
shmoove
I have a game with AI entities in a free plane, not on a grid or a tile. The way I taught them to chase me was by saying:
1 - travel in a straight line towards me
2 - given a set range of visibility, check to see if you see an obstacle between us
draw a line and check for intersection of the bounding box of my obstacles
3 - then draw lines that swing out in either directions to see which direction gets you past the obstacle quickest.
4 - follow that new line for this step of motion
5 - repeat
> 1 - travel in a straight line towards me
> 2 - given a set range of visibility, check to see if
> you see an obstacle between us
> draw a line and check for intersection of the
> bounding box of my obstacles
> 3 - then draw lines that swing out in either
> directions to see which direction gets you past the
> obstacle quickest.
> 4 - follow that new line for this step of motion
> 5 - repeat
Not a bad solution!!!
I'm also thinking preemptive path-finding is too complex for what I need.
I'm not allowing the charachter to move to far places (off screen) and my obstacles are pretty big and not complex (no dead ends).
Now, how do you accomplish step 3?
Do you variate the angle and draw the lines?
From your experience is it a smart method? I mean, does it work well?
Does the pursuer ever lose track of you (except when you want it to) and just get stuck?
So far as I've tested it they haven't gotten stuck.
The best way I can think of to do it is with the Line2D.Double class.
- I draw a line between me and the enemy
- create two lines that are equal to that first line
- rotate the first line, from the enemy, to the left
- rotate the first line, from the enemy, to the right
- if both still intersect the obstacle, I rotate the two again
- if one of them no longer intersects the obstacle, that new line becomes my path
Once the clear path is found, I can use the endpoint of that line as the destination, rather than saying that MY coordinates are the destination. It takes a lot of math figuring so it gets messy written out, but in words it's very clean :)
For simplicity you could try:
- if he hits an obstacle do the following:
- draw a line between the entity and the center of the obstacle
- if you're on the left side of that line, make him turn left 90 degrees
- if you're on the right side, turn right 90 degrees
Based on how you're creating your obstacles you could think further how you want to do it, like tell them to move in that direction a set distance, that sort of thing.
Or you could give them set paths to follow, that's another solution, and just have them be able to aim at you freely to fire, provided that's how they attack.
