|
| 15 Aug 2013 03:03 AM |
But how do I generate the graph for practical use in Roblox? What are your tips?
The Unwise Wizard of Scripters has spoken. |
|
|
| Report Abuse |
|
|
woot3
|
  |
| Joined: 10 Nov 2008 |
| Total Posts: 3599 |
|
|
| 15 Aug 2013 05:25 AM |
I calculated a path, then I calculated a smaller path along that path. So, a 10x10, then a 5x5 then a 1x1. For a stamper place, 16x16, 8x8 then 4x4.
|
|
|
| Report Abuse |
|
|
Aerideyn
|
  |
| Joined: 16 Jan 2010 |
| Total Posts: 1882 |
|
|
| 15 Aug 2013 07:10 AM |
using each integer coordinate as a node is a pretty simple and effective way if your map is pretty flat - other than that there are methods of building nav-meshes by voxelising your geometry into regions which can be reached from any other point in the same region.
then its a matter of triangulating...
A general solution is a huge job - you are probably better off manually creating the graph or simplifying the problem. |
|
|
| Report Abuse |
|
|
|
| 15 Aug 2013 06:38 PM |
I have an idea.
For every Part, lay out a grid of nodes on the top surface, and then the adjacent nodes are connected based on two criteria: • A ray between them yields no intersection. • The height difference them is small enough to merit the connection.
There also has to be something to account for doors. If a ray intersects with a door, it's signified as a "door" edge. Secret doors will have to be ignored, and key requiring doors will have to ignored too.
Also, there are elevators. So, there could be two sets of nodes for both states of the elevator, and both sets are connected.
A little simple, a little complicated. |
|
|
| Report Abuse |
|
|
| |
|
|
| 15 Aug 2013 06:43 PM |
You could also check the distance every node is from the target (ignoring walls), and then keep having the thing move towards the thing that is the shortest distance away. If it encounters a wall, have it turn and keep moving until it's near another space that is closer to the thing than where it is.
So basically a greedy path finder that follows along walls. Not very efficient but neither am I |
|
|
| Report Abuse |
|
|
woot3
|
  |
| Joined: 10 Nov 2008 |
| Total Posts: 3599 |
|
|
| 15 Aug 2013 06:44 PM |
| Surely for bots it is smarter anyway to generate the path progressively? I mean, it can mean that bots travel in longer routes to reach the goal but it means you can have moving obstacles. |
|
|
| Report Abuse |
|
|
|
| 15 Aug 2013 06:46 PM |
Another fantastically lazy one I came up with is that as the bots chase their target, they record the path their target is following. That way, when the target goes around the corner the bots can just follow the target around the corner the target went around.
Then that brings in the target just zig-zagging, so you could then make it go towards the farthest target point that is in it's view. |
|
|
| Report Abuse |
|
|
|
| 15 Aug 2013 06:50 PM |
Whilst AI is cool and all, the problem is that its incredibly unrealistic in its use:
A person does not always go the fastest route. I mean: You will have certainly walked around for 30 minutes only to have displaced a few meters (Or feet, if you use that unit).
Really, I think somebody needs to make an AI that gets the three shortest routes and tells the AI to randomly choose one, and probably then give it a higher weight in later use (Because people like doing things routinely, don't they?) |
|
|
| Report Abuse |
|
|
|
| 15 Aug 2013 06:52 PM |
| Or we could just do what Pokemon does and have enemies randomly appear so they won't HAVE to reach you! :D |
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 15 Aug 2013 06:52 PM |
@Notun
What you're really looking for is an AI that only is given limited information around it's environment, and thus calculates the fastest path from that.
The one way to do that is to halfway calculate A* and then go with the best path. It will dynamically recalculate it's position to get to the end. |
|
|
| Report Abuse |
|
|
|
| 15 Aug 2013 06:52 PM |
| Cant see it working in 3D. |
|
|
| Report Abuse |
|
|
Sorcus
|
  |
 |
| Joined: 29 Nov 2010 |
| Total Posts: 3775 |
|
|
| 15 Aug 2013 06:54 PM |
^ I don't know what you mean by that. We definitely as humans compute the shortest path in our minds. We don't necessarily follow it. And our heuristics for shortest path is just different. It's based on our previous knowledge, fastest time, fastest distance sometimes a combination. Unfortunately with the current computing hardware standards doing this in a game is not feasible.
-- Sorcus |
|
|
| Report Abuse |
|
|
|
| 15 Aug 2013 06:54 PM |
| The problem though is that the route might be complicated (Such as turning around and going in the opposite direction for a bit) where people would know to not do it, and if given proper instructions the AI would, but a halfway pathfind might lead them to a nonsense location. |
|
|
| Report Abuse |
|
|
|
| 15 Aug 2013 06:56 PM |
"We definitely as humans compute the shortest path in our minds."
I have been with people as they walk a distance of about a kilometre to have a displacement of about 50 metres... |
|
|
| Report Abuse |
|
|
woot3
|
  |
| Joined: 10 Nov 2008 |
| Total Posts: 3599 |
|
|
| 15 Aug 2013 07:47 PM |
Generate dynamically if you want to be realistic. Aim for an idea, that's much like how the mind calculates a path.
If you're looking to go north west, but you can only go directly west, east and south. Unless you could see that the west is a dead end, that would be the first path you would take. Eventually you'll learn it's a dead end, and take the next most probably. East as south takes you in the opposite direction.
So yeah .... maybe I'll write something that does this. |
|
|
| Report Abuse |
|
|
|
| 15 Aug 2013 07:51 PM |
But then, depending on communication abilities your AIs will have in the situation, you must also alert certain AIs to ignore that path (And also make it so that the AIs themselves will ignore that path in future), but then you have the problem of doors and stuff. If a door is closed and locked, the AI should not magically know its locked, and still attempt that path (only to discover its locked).
Also, do any games ever have AIs getting lost in buildings? They always seem to know the way around, even if they are not supposed to have been there before. |
|
|
| Report Abuse |
|
|
woot3
|
  |
| Joined: 10 Nov 2008 |
| Total Posts: 3599 |
|
|
| 15 Aug 2013 07:56 PM |
I downgraded A* a while ago and had AI's walking in circles eventually realizing to take another path out. Just make it always go forward, if it meets its own path, it's gone in a circle, try another direction avoiding the original path where possible.
For doors, treat them all as locked but points of interest so when an AI is close it can go and check it out if it can see it, unless it's checked it before and it was locked, in which case ignore it and maybe check less frequently. |
|
|
| Report Abuse |
|
|
magnalite
|
  |
| Joined: 18 Oct 2009 |
| Total Posts: 2467 |
|
|
| 15 Aug 2013 08:19 PM |
| There is a problem with this though. If an ai is trying to find a player, chanced are the player cant see them, and when they can, so can the ai so its then a straight line path. Why over complicate an ai when the user never sees the complicated part? |
|
|
| Report Abuse |
|
|
|
| 15 Aug 2013 08:20 PM |
| Because if you have a glass maze, they can see the complicated bit. |
|
|
| Report Abuse |
|
|
woot3
|
  |
| Joined: 10 Nov 2008 |
| Total Posts: 3599 |
|
| |
|
magnalite
|
  |
| Joined: 18 Oct 2009 |
| Total Posts: 2467 |
|
|
| 15 Aug 2013 08:28 PM |
| It would actually be really easy to implement this without too much extra processing (although i'm thinking of a node based map, not sure about a navmesh). |
|
|
| Report Abuse |
|
|
FusiaOS
|
  |
| Joined: 11 Aug 2013 |
| Total Posts: 99 |
|
|
| 15 Aug 2013 11:11 PM |
The way I did my 3d pathfinder using A* was I created a script to make nodes... here is how that worked...
I put parts on the map(nodes) in spots I considered to be safe to navigate. Then I had a script start at one node and raycast to every other node. Thus finding which nodes were in its sight. Then it created a table with nodes that could connect and then it printed a string version of said table and I pasted that table into my script as the graph.
This is good for static maps. Then everytime a path was found from one node to another, it saved that path into a table with an index of:
Node1Name:Node2Name
Then when looking for a path, first it would look for previously found path, if not found it would find one and then store it into the map of found paths.
|
|
|
| Report Abuse |
|
|
magnalite
|
  |
| Joined: 18 Oct 2009 |
| Total Posts: 2467 |
|
|
| 15 Aug 2013 11:18 PM |
@FusiaOS
Exactly how mine works lol. Except I'm working on making mine pre process every possible path then output a string so i can rebuild that instead of processing again. |
|
|
| Report Abuse |
|
|