Pathfinding AI
BlitzMax Forums/BlitzMax Beginners Area/Pathfinding AI
| ||
Well, after coding my first AI idea, I realize that it doesn't work as well as I thought it would... So I was thinking about finding a path to the player when the enemy is created, and then just follow it:![]() Here for example, it gets an initial straight path to the player and checks if it collides with something. If not, great, follow it. If it does, in this case, that gray thingy, then it checks for alternatives. ![]() Here it went up a bit, and then straight to the player. But it's still not perfect. ![]() Now it can reach the player without colliding with anything. But that's a damn ugly path. Until now, I can do it on my own, saving the path in a list of points and following it. ![]() So, it takes the point that deviates from the original path the most, and makes it the half point of a curve between the player and the enemy. But I have no idea how to do that. I have two ideas, one using sin and cos, the other just taking the axis with the smallest difference, in the image above it would be Y, and add successive values, lowering every time. Did anyone ever have to do this? Will this be resource-consuming? |
| ||
here is a easy "realtime" algoritm for such pathifinding... i don't know the name of it... but i think you can write your own routine... the basic-idea... source is the top point and dest is the bottom point... so that your object can "roll" from top to down... if you have a object in the moddle - this generate a small hill - so that your object automaticaly do not collide with this... you need this: -dest coord -current coord -all collide coords + collide factor from all this coords you can calculate delta coords to move your object... you should normalize delta to 1 and multiply this with speed factor... i have no formulas... but i think this is smilar to this: http://en.wikipedia.org/wiki/Metaballs http://de.wikipedia.org/wiki/Metaball but this algo is not perfect - it have problems with complex scenes (labyrinths) - i do not know - do you have labyrinths? |
| ||
Toward More Realistic Pathfinding . on Gamasutra. You might need to register (unless you can search and find the article somewhere else) but well worth it. |
| ||
Well actually I don't plan to create any labyrinths, but in later stages there will be a lot of rocks, meaning the enemies will have to dodge several times, maybe make several turns to reach the player. So I think I don't need something very complex. I have to leave now, I'll read the links you gave me as soon as I'm back. Thanks tonyg :) |
| ||
Your last comments suggest you might want to look at Steering Behaviours for which Scott Shaver created a module Here's some more info. |
| ||
Sorry McCredo I thought your post was also by tonyg, so I forgot to say thanks... So thanks :) Your idea would work too but I think the steering behaviours are more appropriate in this case. tonyg: I think that will do just great, will try it as soon as I get home. Thanks. |
| ||
Hello. The "standar" pathfindig algoritm A* es useful for you. One system for make your movement is increment the cost of nodes proportionally to the distance to grey player. Low distance -> high cost high distance -> low cost The A* make your curve automatically I write a pathfinding function really fast. it take in my machine 4.5 seg in traverse a map of 100000 nodes and only 384 millisec for a map with 10000 nodes. All nodes are traversables in 8 directions with a random cost. If not all nodes are traversables the time is reduced. The algoritm is useful with any number of directions. If you need it talk with me. It is free :-) Bye, Paposo |
| ||
Isn't the needed code not already in the forum ? Click here! |
| ||
Hello. Yes xMicky. This is only another point of view of same algorithm. The indiepath es very very fast. My routine more slow. Diferences: Indie algorithm: - Use rectagular cells in a matrix - two dimensional paths - Fixed heuristic - Directions fixeds - Dependance algorithm - map - Construct the nodes automatically - All the nodes are identically - Very especific Paposo algorithm: - Not use cells in any matrix - N dimensional paths - Customizable heuristic - Directions variables for each cell - Independance algorithm - map - The user construct the nodes - Allowed diferent node, costs and heuristic implementations in same map - Very generic The objectives of routines are distincts. I have in developement more optimized routine. I are regarding the fast-fast indie code for make optimizations in my code. ;-) Bye, Paposo |
| ||
hm... if i have time, i write this routine, i decribed above... it is good for not complex scenes - with many moving objects - and you need only few simple calculations and if something changes - you get the result at "realtime"... You do not need cells and you do not need predefined paths/grids. You do not get a path to destination, but you get only a moving direction. And in theory you sohuld have smooth movement. |
| ||
Paposo I would like to take a look at your code, if you don't mind. My e-mail and MSN is mothmanbr@... Thanks. |
| ||
Hello M07hM4n. This version are more optimized . It take 24 millisec in 1 million nodes in my machine. For fast algorithm the cost fixed + modifier equilibrated with heuristic. For optimal path heuristic low than (costfixed+modifier) The user adjust factorPA, fixed cost, modifiers for penality certains directions, and heuristic for your pourpose. It make de algorithm more fast or slow. Sorry. All coments are in spanish This is the code: This is a example with 1000000 nodes and 8 directions if you need explain answer me Bye, Paposo |
| ||
Thanks Paposo, do you expect a mention in the special thanks section of the credits? :P And don't worry about the spanish, I speak portuguese and can handle myself with it. |