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 » Scripting Helpers
Home Search
 

Re: Path Finding

Previous Thread :: Next Thread 
warspyking is not online. warspyking
Joined: 15 Nov 2011
Total Posts: 13947
05 Jun 2014 01:36 PM
Alright, Say I build an epic maze, how could I make a script that would find the path and then highlight it..?

I read the wiki. Help?
Report Abuse
warspyking is not online. warspyking
Joined: 15 Nov 2011
Total Posts: 13947
05 Jun 2014 01:51 PM
Anybody..?
Report Abuse
robertjh12 is not online. robertjh12
Joined: 24 Feb 2008
Total Posts: 601
05 Jun 2014 01:51 PM
You mean find the path to the end?
Report Abuse
warspyking is not online. warspyking
Joined: 15 Nov 2011
Total Posts: 13947
05 Jun 2014 01:55 PM
Yes, I want to make a brick that will determine the path through a maze beforehand, then will glide through it leaving a trail.


I can handle the trail, I need help with the path finding
Report Abuse
robertjh12 is not online. robertjh12
Joined: 24 Feb 2008
Total Posts: 601
05 Jun 2014 01:56 PM
If you want to find path to end of a maze, create a block at every intersection. Have a ray sent from each block to the next intersection. Eventually you will hit the exit with a ray.
Report Abuse
robertjh12 is not online. robertjh12
Joined: 24 Feb 2008
Total Posts: 601
05 Jun 2014 01:57 PM
If you don't like above idea, do same thing for intersections, but only ones leading to exit. Then make the brick path to the next block on way to exit.
Report Abuse
warspyking is not online. warspyking
Joined: 15 Nov 2011
Total Posts: 13947
05 Jun 2014 01:58 PM
I don't want to make a block at every intersection...
Report Abuse
VerifiedName is not online. VerifiedName
Joined: 26 Jul 2009
Total Posts: 4534
05 Jun 2014 01:58 PM
so you're asking for a full pathfinding script?

Report Abuse
warspyking is not online. warspyking
Joined: 15 Nov 2011
Total Posts: 13947
05 Jun 2014 01:59 PM
I'm going to be making a game about mazes, there will be user created mazes with blocks at intersections...


Also the point is to FIND the way through, not just know it and use it.
Report Abuse
warspyking is not online. warspyking
Joined: 15 Nov 2011
Total Posts: 13947
05 Jun 2014 02:00 PM
@ver

No I'm asking for help on how to do it...
Report Abuse
warspyking is not online. warspyking
Joined: 15 Nov 2011
Total Posts: 13947
05 Jun 2014 02:24 PM
Help
Report Abuse
BJCarpenter is not online. BJCarpenter
Joined: 04 Nov 2008
Total Posts: 4416
05 Jun 2014 02:28 PM
Look-up path-finding on the Internets, and u will get psudo-code which u can turn into Lus code....

If it is a true maze (mostly no open areas, and fairly regular), you can do 'wall-hugger' (Don't know the actual name) Left or Right (or both, then pick the shortest). Left:

1) When u come to a wall; turn left (90 degrees) (else go forward); If another wall, turn left (If still wall, after one more turn, then u r trapped: Jump or something).

2)Move forward one unit; Turn Right; Goto step 1


"Right Wall-hugger" code is the mirror of "Left"

"Patroling NPC with AI", in the Catalog, uses 'wall-hugger' logic....

GL,
Brian
Report Abuse
Gorake is not online. Gorake
Joined: 10 Feb 2014
Total Posts: 219
05 Jun 2014 02:29 PM
Are the mazes going to be aligned on a grid?
Report Abuse
BJCarpenter is not online. BJCarpenter
Joined: 04 Nov 2008
Total Posts: 4416
05 Jun 2014 02:30 PM
*1) When u come to a wall; turn left (90 degrees) (else go forward; Goto 1);
Report Abuse
Gorake is not online. Gorake
Joined: 10 Feb 2014
Total Posts: 219
05 Jun 2014 02:37 PM
BJ that would only work if there was never two dead ends facing each other, with a branch between them.

A very simple, but maybe not the most efficient, process could be:

1. Start tile
2. Cast rays in all 4 directions with a length of 1 tile. Keep track of where these rays were sent from.
3. For each ray that hit nothing, repeat step (2) for only the directions not explored.
4. When exit tile is reached, track the rays backwards from where they were sent to get the path in reverse.
Report Abuse
BJCarpenter is not online. BJCarpenter
Joined: 04 Nov 2008
Total Posts: 4416
05 Jun 2014 02:53 PM
Gorake,

No 'wall-hugger has no problem with Dead-ends of any number; it just U-turns out of them, eventually.

It IS a wall-hugger: It WILL get out of any Maze; it will NOT find the shortest route.
Report Abuse
BJCarpenter is not online. BJCarpenter
Joined: 04 Nov 2008
Total Posts: 4416
05 Jun 2014 02:59 PM
And you could always just delete the dead-end section from your route. if you ever land on a tile which u have already been to.
Report Abuse
Gorake is not online. Gorake
Joined: 10 Feb 2014
Total Posts: 219
05 Jun 2014 03:00 PM
Sorry, I understand the wall-hugger concept, I was just a bit confused by your directions. I get it now.
Report Abuse
AgentFirefox is not online. AgentFirefox
Top 100 Poster
Joined: 20 Jun 2008
Total Posts: 22404
05 Jun 2014 03:03 PM
If you use a grid system, you can totally use A*.
Report Abuse
warspyking is not online. warspyking
Joined: 15 Nov 2011
Total Posts: 13947
05 Jun 2014 03:05 PM
Interesting...



So basically, to do that I'd need a link back. That could work :P


But what do you mean by one "tile"?
Report Abuse
BJCarpenter is not online. BJCarpenter
Joined: 04 Nov 2008
Total Posts: 4416
05 Jun 2014 03:06 PM
TaKE "pATROLing NPC with AI". Flip GraphicsToggle, in the AIPatrol script to True, so u can watch the order in which the Rays are cast.

First it shoots two rays: one 7 studs forward to check for wall, and one straight down (from 7 studs forward) to check for floor....

If False and True then walk forward, else shoot a Ray to see if we can Jump forward, else Turn Left; repeat.
Report Abuse
Gorake is not online. Gorake
Joined: 10 Feb 2014
Total Posts: 219
05 Jun 2014 03:06 PM
That's why I asked if it was lol.
The only problem with A* is that it probably wouldn't do much better than Dijkstra's in a maze situation.
Report Abuse
Gorake is not online. Gorake
Joined: 10 Feb 2014
Total Posts: 219
05 Jun 2014 03:08 PM
One tile = one section on the grid, measuring the width of corridors on each side.
Report Abuse
warspyking is not online. warspyking
Joined: 15 Nov 2011
Total Posts: 13947
05 Jun 2014 03:13 PM
So


1) Keep raycasting ahead 1 stud until there's a wall.
2) Turn 90°
3) Go back to 1 and continue until exit found.
4) All the while leave a trail



That would end up making it go backwards at a dead end, making wrong paths...
Report Abuse
ForeverDev is not online. ForeverDev
Joined: 04 Oct 2008
Total Posts: 13300
05 Jun 2014 03:17 PM
@War

Look up A* pathfinding on Google. I've never been able to do it.
Report Abuse
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripting Helpers
   
 
   
  • 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