Welcome, Guest. Please login or register.

Login with username, password and session length

 
Advanced search

1411273 Posts in 69323 Topics- by 58380 Members - Latest Member: bob1029

March 28, 2024, 02:16:07 AM

Need hosting? Check out Digital Ocean
(more details in this thread)
TIGSource ForumsCommunityTownhallForum IssuesArchived subforums (read only)TutorialsBraving Procedural Generation
Pages: 1 ... 21 22 [23]
Print
Author Topic: Braving Procedural Generation  (Read 212672 times)
gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« Reply #440 on: July 02, 2013, 02:35:42 PM »

Where I can learn more about this planner?
Logged

BleakProspects
Level 4
****



View Profile WWW
« Reply #441 on: July 02, 2013, 02:53:44 PM »

Rapidly Exploring Random Tree, the biDirectional one "RRTConnect", is the one I'm showing here. Basically, it works by randomly growing a collision-free tree from the start position and returning a path it finds which just happens upon the goal position. In RRTConnect, you grow two trees, one from the start and the other from the goal. When they meet, you have the path from the start to the goal.

It's extremely simple to implement (RRT has like 5 lines of code tops. RRTConnect can be written down with like 20 lines). It does not work as well as A* in 2D cases and can produce some terrible paths. However, if you have greater than 4 dimensions, it's the easiest and often the best and fastest planner you can use to find feasible (not optimal) paths. An optimization procedure can be run on the resulting path to make it shorter and more optimal.

An example where it might be very useful in a video game is if you have a character that can freely move around a 3D world *and rotate*. This is called the "Piano Mover's Problem." If you tried to run A* naively in this space you will quickly run out of memory. You could make A* work in this space only by doing clever and very complicated techniques involving lazy evaluation and anytime, heirarchical planning. These techniques are often very difficult to understand and end up being fairly slow anyway. This is because A* is necessarily an *optimization* procedure. It is trying to find the "best" path.

In contrast, an RRT will often give you a "good enough" path much much faster than A*, and in expectation will use far less memory than A* for high dimensional problems.
« Last Edit: July 02, 2013, 03:03:08 PM by BleakProspects » Logged

gimymblert
Level 10
*****


The archivest master, leader of all documents


View Profile
« Reply #442 on: July 02, 2013, 08:35:37 PM »

That sound pretty cool thanks for sharing, it looks rather promising to do procedural design too (and city layout generation), it have very organic looks. By your description it looks like it was inspired by rhizome growth (which why it caught my eyes to begin with!).
Logged

Pages: 1 ... 21 22 [23]
Print
Jump to:  

Theme orange-lt created by panic