Need help about pathfinding.
Author
Hi everyone,
In my game there is a car(computer ai) trying to hit a pedestrian(player). The rules:
Car's manoeuvre capability is limited. The car can do the rotations in a certain angle but of course it is faster than the pedestrian.
Pedestrian can walk in any direction. So the manoeuvre capability is not limited. But of course the player is slower than the car.
In the game there will be obstacles and a 3d terrain.
How can I implement a patfinding algorithm to hit the player.
If they move at a constant rate the player will always be in a certain radius, however if I implement any terrain restrictions things will even get more complicated.
What kind of algorithm should I use for pathfinding within this environment? I read a little bit about A* but I will not have grids here.
I hope I've explained the problem good.
Thanks.
Im not 100% sure on this as i always used a grid whenever i did my pathfinding, i would assume that you'r going to have to use some kind of grid. To accomplish what you want, however im not sure on what type of algorithm you would need to implement, the A* might be expensive if your going to have many cars and man y other algorithms, but again im not exactly sure about this. I would definetly recommend having some kind of grid or other data structure to hold your terrain and the character, that should definetly simplify the process.
Unless you want to simply use something like just generally move car towards the persons location at a set speed, however this doesnt really take into account the terrain
Fallout
Unless you want to simply use something like just generally move car towards the persons location at a set speed, however this doesnt really take into account the terrain
Fallout
This isn't really a pathfinding problem. It's more of a feedback-based decay to equilibrium (have a look at PID Controllers), with surrounding-awareness playing a secondary role.
Path grid data doesn't account for velocity and moments of ascent angle, both of which which play critical roles in the situation. You'd be better off with a simple feedback loop based on some rules like:
1. If the car has just missed the pedestrian, brake.
2. If the car is on course to hit the pedestrian, accelerate.
3. If the car is not on course to hit the pedestrian but is capable of doing so, turn in the appropriate direction by a reasonable amount.
...
You'll obviously need some margin cases to deal with obstacles. The form of this rule-set also suggests that a finite-state machine may be appropriate (attacking, recovering, lining-up etc.).
This is just what comes to the top of my head though - I'm sure you could come up with a more effective rule-set with a little thought.
Admiral
Path grid data doesn't account for velocity and moments of ascent angle, both of which which play critical roles in the situation. You'd be better off with a simple feedback loop based on some rules like:
1. If the car has just missed the pedestrian, brake.
2. If the car is on course to hit the pedestrian, accelerate.
3. If the car is not on course to hit the pedestrian but is capable of doing so, turn in the appropriate direction by a reasonable amount.
...
You'll obviously need some margin cases to deal with obstacles. The form of this rule-set also suggests that a finite-state machine may be appropriate (attacking, recovering, lining-up etc.).
This is just what comes to the top of my head though - I'm sure you could come up with a more effective rule-set with a little thought.
Admiral
I agree with TheAdmiral that a behavior based approach would work better than a path finding approach. You might look into the "boids" model of flocking behavior. You can find a ton of info here. There is source near the bottom that includes obstacle avoidance. Just create your own set of rules and you should get some interesting behavior. This would also lend itself to having several cars, each one modelled as a boid, and each following a set of rules. The rules are simple:
Drive towards the pedestrian.
Steer away from other cars.
Steer away from obstacles.
Just make sure you are steering and driving the car by applying some force to it and not just snapping its direction to match the desired direction (see TheAdmirals link on PID Controllers). This can give rise to some neat gameplay. You could provide paramters that govern how fast the car can turn such as reaction delays, maximum turning radius, etc. Depending on how fast the cars can turn, the player can try to force them to ram into obsticles or each other.
Drive towards the pedestrian.
Steer away from other cars.
Steer away from obstacles.
Just make sure you are steering and driving the car by applying some force to it and not just snapping its direction to match the desired direction (see TheAdmirals link on PID Controllers). This can give rise to some neat gameplay. You could provide paramters that govern how fast the car can turn such as reaction delays, maximum turning radius, etc. Depending on how fast the cars can turn, the player can try to force them to ram into obsticles or each other.
Author
Thanks for the suggestions. I guess I will start first with a flat terrain (in other words 2d) and no obstacles. It may be a better idea to go step by step.
I partially agree that a behavior based approach would work better than a path finding approach, but not that they are two seperate things there should be a mix and match of both to obtain a good result.
I also agree with you that should go one step at a time so that you understand the entire process better.
But I would recommend that you take a look at "OpenSteer", looks like it would suit your case pretty well.It is a nice library and has some really nice demos and tutorials that will help you alot.
EnygmyX.
I also agree with you that should go one step at a time so that you understand the entire process better.
But I would recommend that you take a look at "OpenSteer", looks like it would suit your case pretty well.It is a nice library and has some really nice demos and tutorials that will help you alot.
EnygmyX.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
