generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Re: Plausibility of Pathfinding

Previous Thread :: Next Thread 
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
BlueTaslem is not online. BlueTaslem
Joined: 11 May 2008
Total Posts: 11060
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
BlueTaslem is not online. BlueTaslem
Joined: 11 May 2008
Total Posts: 11060
22 Aug 2013 08:03 PM
You really can't get much faster than A* in general...
Report Abuse
MHebes is not online. 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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
22 Aug 2013 09:41 PM
Found out on this:

http://stackoverflow.com/questions/1351746/find-a-tangent-point-on-circle
Report Abuse
MHebes is not online. 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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
22 Aug 2013 11:54 PM
Now I have ran into problems... They just sit at the edge of the circle :/
Report Abuse
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
23 Aug 2013 12:01 AM
Have a look at the problem here: http://www.roblox.com/item.aspx?id=14551284
Report Abuse
FusiaOS is not online. 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 is not online. Oysi
Joined: 06 Jul 2009
Total Posts: 9058
23 Aug 2013 02:56 AM
[ Content Deleted ]
Report Abuse
HEAT507 is not online. 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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Notunknown99 is not online. Notunknown99
Joined: 05 Sep 2008
Total Posts: 25360
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
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image