|
| 22 Aug 2013 07:56 PM |
Ok, so the pathfinding algorithms I have seen tell AIs where they CAN go, I had an idea to instead tell AIs where they CANNOT go.
So the idea is this:
You dot a map with 4 or 5 circles which are the "no-go" zones and then when the AI is attempting to go from A to B it checks if the line intersects any circles and, if so, it instead draws the path at a tangent to the intersecting circle (It will assume that the radius is 1 bigger than the circle) (if the new line intersects a circle it will go to the edge of that). It will repeat this until there are no intersections and it has reached the target.
Before I go about making this, I want to ask how plausible you think this is for an AI. My game does not need super-advanced AIs that will solve a maze, as the game will only have a few (5 or 6) areas that are just for effect anyway. |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 07:58 PM |
| And, for simplicity, it will work purely in 2D, and no two circles will be near each other (They will be quite spaced out) |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 08:00 PM |
| In general, you just make paths high-cost if you don't want the search to go through them. That way, it will avoid them at very high costs, but eventually choose to go through if that's the only [reasonable] way. |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 08:02 PM |
| But I am worried that if I were to use a Dijkstra or A* I wouldn't get as smooth a path and it would be slower... Its not a very maze game (Just some placed scenery) and I am only really wondering if it will be much faster than a Dijkstra network. |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 08:03 PM |
| You really can't get much faster than A* in general... |
|
|
| Report Abuse |
|
|
MHebes
|
  |
| Joined: 04 Jan 2013 |
| Total Posts: 2278 |
|
|
| 22 Aug 2013 08:07 PM |
What you're describing is a navigation mesh, but you're creating it in reverse, basically. So yeah, it would probably work pretty well, but if you want it to be a bit more versatile I would suggest looking into a normal navigation mesh instead.
~ Oh, I'm sorry, did I break your concentration? ~ |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 08:30 PM |
1: Cannot find anything on normal navigation meshes
2: Wouldn't this be faster than A*? You only have to calculate if its within a circle (Which is VERY simple, just linear inequalities). I mean, its not as versatile, like MHebes said, but I do not need it to be. |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 08:32 PM |
Not linear inequalities, this is not linear :/
SIMILAR to them, or something like that. IDK, its what failed me Decision 1... |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 08:45 PM |
| Now, how should I go about getting the nearest target... Should I just use magnitude, or calculate the path for each player, adding 5 if it intersects a circle..? |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 08:51 PM |
| Now I just need to find a way to tell if the line segment intersects a circle and, if so, create a line that is a tangent to the circle that passes through A... |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 08:59 PM |
I am using this article:
http://doswa.com/2009/07/13/circle-segment-intersectioncollision.html
And will have to later find out how to make the tangent.
This is looking good so far! :D |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 09:26 PM |
Right, now it knows if it intersects a circle.
I just need to make a tangent to that circle... |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 09:33 PM |
I am having problems finding anything.
Anyone know some good tutorials? Preferably with diagrams; I find it easier to learn with diagrams. |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 09:41 PM |
Found out on this:
http://stackoverflow.com/questions/1351746/find-a-tangent-point-on-circle |
|
|
| Report Abuse |
|
|
MHebes
|
  |
| Joined: 04 Jan 2013 |
| Total Posts: 2278 |
|
|
| 22 Aug 2013 10:09 PM |
That was a fun read, and I appreciate the not-meaningless bumps :P
~ Oh, I'm sorry, did I break your concentration? ~ |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 10:11 PM |
| I have got it half-ish working... It wont get the shortest route, so I need to fix that :/ |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 10:26 PM |
| Acquired h4x and used it to get the shortest route (Or a guess at it, anyway. I am not going to get the shortest route because of lag issues) |
|
|
| Report Abuse |
|
|
|
| 22 Aug 2013 11:54 PM |
| Now I have ran into problems... They just sit at the edge of the circle :/ |
|
|
| Report Abuse |
|
|
|
| 23 Aug 2013 12:01 AM |
| Have a look at the problem here: http://www.roblox.com/item.aspx?id=14551284 |
|
|
| Report Abuse |
|
|
FusiaOS
|
  |
| Joined: 11 Aug 2013 |
| Total Posts: 99 |
|
|
| 23 Aug 2013 01:22 AM |
You could tell it where it can't go all day long, but if you do that....
1. It won't find a quick path there. 2. It will ramble around randomly 3. 1 and 2 are enough. 4. If it does get there it will be almost a miracle |
|
|
| Report Abuse |
|
|
Oysi
|
  |
| Joined: 06 Jul 2009 |
| Total Posts: 9058 |
|
| |
|
HEAT507
|
  |
| Joined: 31 Aug 2012 |
| Total Posts: 429 |
|
|
| 23 Aug 2013 03:20 AM |
is if saying : if theres a safe spot in the map that the user is on they can't go there you got me on this one it won't happen agian. |
|
|
| Report Abuse |
|
|
|
| 23 Aug 2013 09:47 AM |
90% fixed!
A few AI quirks, but I can sort those out later.
6 Zones, 128 AIs, ~0.01 seconds (As of now)
I am happy with this :D |
|
|
| Report Abuse |
|
|
|
| 23 Aug 2013 09:51 AM |
Removed some unused values, managed to get the time down a bit :D
I am very happy with this right now :) |
|
|
| Report Abuse |
|
|
|
| 23 Aug 2013 10:06 AM |
When all the zombies start moving it lags... Even when I set the scripts Disabled property to true.
Is this my script or Roblox? |
|
|
| Report Abuse |
|
|