A.I/ Pathfinding help (agaaaiiin)
Blitz3D Forums/Blitz3D Beginners Area/A.I/ Pathfinding help (agaaaiiin)
| ||
| ok, so i am apparently not smart enough/creative enough to find a good way to do pathfinding in blitz3d. I am starting from scratch again, but i need some very intelligent help (someone who could walk me through it and explain tid-bits of it to me :P ) so I know this is not exactly something people are going to be piling up to help me with but if you could find it in your heart i would be very very glad. I am working on a game right now and the main element holding me back at this point is the pathfinding cause it is so stuck in my head!n if i can get help with this i will be sure to help instruct others under the condition that they do the same so maybe we can have an instructed group in the art of pathfinding... :) |
| ||
| Well, how is your game map structured? There are lots of ways of doing pathfinding... what sort of game is it? Do the paths need to be calculated real-time or can you pre-calculate the pathfinding? I know someone is going to simply reply and say "look up A*" but that is not necessarily what is best depending on your game... For example - if you are building a game with static level environments you could build a series of splines or waypoint paths into your level and make them invisible..then when a unit wishes to travel from one point to another point simply take the relevant spline that goes from 'near' the starting point to 'near' the ending point and follow it... There are a myriad of ways to do pathfinding...some more appropriate for some games than others.... |
| ||
| well, in the end i am looking for an open world game (i know start small) but for now i am looking for just a small fps engine (i will have little problem coding that) but i need to have pathing up and down staircases(3D) and just basic around obsticals and possibly over certain structures depending on the characters agility (per A.I). as for real time or pre-determined i honestly don't know what the different reasons for using one over the other would be. At one time i put a lot of energy and study into this but each time i try i cannot make the code fit it's purpose. so sorry by the way cause although i have gotten plenty of help my brain is completely stubborn so i might need some help figuring out what i need :P sorry D: again i am a quick and fairly good programmer (though it has been awhile) just can't tackle this one alone. |
| ||
| bump |
| ||
| Here an example : http://www.melog.ch/dl/astar3D_2.zip And here another example : http://mrpye.com/Blitz/Pathfinding/pathfinding.htm Last edited 2012 |
| ||
| yeah, if you read my original post, i'm not having trouble finding examples but actually understanding and utilizing them. |
| ||
| bump :/ |
| ||
| As said there are lots of ways of doing this...and so I'm not sure which one to exactly suggest... Probably the easiest way to handle pathfinding that looks semi natural for an RPG with not too many (ie say about 10 - 20 NPCs wandering around in proximity to the player) characters at one time - which I've used in the past is this: Have a state for your AI units. One is 'wander' the other is 'go to'. Wander is, as the name implies, just a state where the AI wanders near to their shop/location. Go to is where the AI heads for a specific character, position or otherwise. What you do is perform a line pick to the position you wish to move to. If the AI can see the position then you simply point the AI in that direction and walk there. If the AI cannot see the position then that means the target position is blocked and something is in the way. In that case you need to decide whether to continue trying to get to the position or to give up. If you decide you wish to continue getting to the position then attempt to set temporary go to targets near the final target position...if these can be seen with a linepick then head for that position instead and when the AI gets there then check to see if can see the true target position...if so then head over there, otherwise repeat process until give up. Note you can make it smarter by building a database of 'locations walked' by the NPCs and players so that they can remember paths taken before...and store it so that it is remembered between games..that way you can train your AI to behave smarter with some practice games in development. from Matt |
| ||
| that actually sounds like 100% of what i would use, not what i had in mind but i think in the end it could work out better! any further help or am i kinda screwed now? if i could find any help implementing this that would be awesome. Last edited 2012 |
| ||
| What you do is perform a line pick to the position you wish to move to. If the AI can see the position then you simply point the AI in that direction and walk there. If the AI cannot see the position then that means the target position is blocked and something is in the way. In that case you need to decide whether to continue trying to get to the position or to give up. I use a similar approach. However i don't check if a character (humanoid) can see a target, i check if the path to go there is free (with a linepick with a radius of 0.25 or with a moving collider sphere with a radius of 0.25) If the linepick or the moving collider sphere have not hited/been collided to an obstacle, then it means the path is free and the character can reach the target. In this case i turn the character towards the target and then i move it until it reaches the target. Please note that this is a good approach only if your character is not able to cross obstacles on which he can jump/climb/fall, else you have to add more checks and rules to the code. In the case the linepick or the moving collider sphere have hited/been collided to an obstacle, then it means the path is obstructed and the character can't reach the target. In this case, i calculate what are the accessible nodes from the character position (again with a linepick with a radius of 0.25 or with a moving collider sphere with a radius of 0.25) From the nodes that are near enough and accessible, i calculate the total distance from Character to Node + from Node to Target. I then chose the smallest distance and the node corresponding to this distance is the first node of my path. I turn the character towards this node and then i move it until it reach the target. During this time, i can calculate a Astar path, thanks to the precalculated links between the nodes. In such a routine, what takes time are the linepicks to check what is the nearest and accessible node from the Character and the linepicks to check what is the nearest and accessible node from Target. This can be optimized by precalculating what are the nearest and accessible nodes from several sub zones (triangles) in the room or by using a nodes on a grid system. Try to create some code with this info so we can see where your problem is. Last edited 2012 |
| ||
| ok i will try and throw together some code, the problem i had before was my method of storing node data (i would bury myself in 'types') but i will take a new crack at this then post some code! |
| ||
| I can explain the concepts in words but if you can't understand the logic of the code examples i have posted, there is no point in posting my code here. Moreover i store most of my pointers and variables in dim arrays, so if you prefer types you will be confused even more. I will try to post an example with comments later but don't count on it soon, i have others things to do now. |
| ||
| Meh, forget all the long explanations, just use this for AI: http://blitzbasic.com/Community/posts.php?topic=89386 |
| ||
| I am trying to create step by step explanations so that you can understand how it works and how to code it. |
| ||
| Meh, forget all the long explanations, just use this for AI: ...on the other hand, if you want to actually learn stuff instead of just letting everybody else do it for you, ignore anything Thundros says. http://blitzbasic.com/Community/posts.php?topic=89386 |
| ||
| Or if you want to learn the EASY way, ignore anything GFK says. He's been on my case forever, and needs to leave me & my posts alone. Anyways, good luck psychicbottle, with GFK, you'll NEED it. |
| ||
| Thundros>>The code by Drak is not about obstacle avoidance, path calculation, path following, it is about the different states a npc may have, and about how to make a npc "chase" the player or go to a target. So you are off topic on this one. |
| ||
| @ Thundros I am not looking for a pre-made code i am looking to learn as much as I can in this field and im looking at pathfinding not basic A.I. but thank you for trying to help still. @GFK im not looking for an "easy way out" on this, I am actually very excited to be learning all i can about pathfinding and am deep in the depths of my own sloppy code i am trying to write but i keep messing up and destroying my code :/ it's on it's way though! @ RemiD thank you very much for all the help so far! |
| ||
| i was running through the archives looking for something related to helping me understand how to code A* and i found this. is this a good code that would be easy enough for me to rip apart and learn from? save this one as "Pathfinding3.bb" |
| ||
| Psychibottle>>If you understand this code and if you can use it for your game, do it ! However, from the first read i had, it seems this is a pathfinding system only for nodes positionned on a grid. I don't use the same approach, i store the parameters of the nodes and the parameters of the links between some nodes in order to avoid useless checks. Also by storing parameters about the links it is possible to use the same routines with nodes positioned around obstacles or manually (not on a grid) I am currently trying to explain each step, check, rule in words, do you still need it or no ? This will only be usefull to you if you want to understand the mechanics in order to code your own routines. If you want a code ready to use you should probably use one of the examples on the forum. Last edited 2012 |
| ||
| I would rather do a manual version as you say and not a grid and i intend to try and code my own here so I would still appreciate the explanation that you're working on :) (not to mention i THINK i may have found a slight bug in the code) |
| ||
| The website is now hosted on another server, hence the missing posts. See my answer here : http://74.86.81.120/~blitzbas/Community/posts.php?topic=99276 |
| ||
| ok, sorry for assuming so quickly there, and thank you for all of your help and i shall post about pathfinding again, once i am ready to undertake it. thank you for all your help :) |
   |