-
Originally Posted by trogdor458
Have a giant maze thing randomly in your level?
Don't waste resources trying to solve it during run-time, just hard-code the solution in there
this is for Online Quest/Adventure Game Editor. i want to make a veeeeeeery easy to use editor so illustrators and designers could just upload graphics, do several clicks and get a game and share it.
-
Pumpkin Carving 2008
Originally Posted by artfabrique
The shapes those vectors make up is irrelevant. What's important in my suggested theory is that you always scan the closest intersection.
The 'Boose':
ASUS Sabertooth P67 TUF
Intel Core i7-2600K Quad-Core Sandy Bridge 3.4GHz Overclocked to 4.2GHz
8GB G.Skill Ripjaws 1600 DDR3
ASUS ENGTX550 TI DC/DI/1GD5 GeForce GTX 550 Ti (Fermi) 1GB 1GDDR5 (Overclocked to 1.1GHz)
New addition: OCZ Vertex 240GB SATA III SSD
WEI Score: 7.6
-
Please, Call Me Bob
Originally Posted by artfabrique
this is for Online Quest/Adventure Game Editor. i want to make a veeeeeeery easy to use editor so illustrators and designers could just upload graphics, do several clicks and get a game and share it.
Well, hrmm
I guess what I would do is when you finish making a level, have it figure out its own efficient set of nodes that can be used later when actually playing the game
Players won't mind waiting a few seconds for processing after they make a level compared to how much they would mind waiting a few seconds every time they want to pathfind somewhere
So basically: player puts in a random maze, computer solves random maze, computer stores solution to maze in the level code so it doesn't have to again later
Lots of programs do this sort of thing, not just for pathfinding
-
M.D.
its called a navigation mesh and like trogdor pointed out the best way is too manually place nodes and connect them up. Its tedious but gives you the best results.
Alternatively you could subdivide the map like a grid and connect up grid nodes to other nodes which do not overlay graphics (using some bitmapData getPixel methods or similar). Then optimize it further by joining empty regions of nodes together, so you end up with a quad tree like structure.
-
formerly hooligan2001 :)
Yeah nodes is the best bet if your not using tiles.
-
Please, Call Me Bob
But he said he'll be unable to make the mesh himself, as he'll need pathfinding for custom-made user-levels, and doesn't want to put them through the tedious process themselves
I can't say I've ever tried it and I don't feel like doing research either, but I have a few ideas on how to automate the process
I could give it a shot =\
-
M.D.
The best approach I have found is to subdivide the area then merge open spaces. Once done the nodes can be created at the grid square edges and link between grid nodes. Its not totally 100% accurate but will give you nice distances from wall edges and is fast to compute.
Another approach is to extrude the end points of walls and create several corners for 1 edge. However, problems can occur when the extrusion falls inside other geometry (corridors and close walls). Figuring out how much to extrude by becomes very costly on the CPU if lots of other geometry exists, you basically have to loop over all geometry and determine distances between walls.
Then comes the problem of linking up nodes to other nodes from other sets of geometry that may be hundreds of pixels away. You must raycast from every edge to every other edge in order to determine the visibility mesh (very expensive), nodes * nodes * walls. You also need to disregard nodes that fall within the extrusion zone, also very bad.
Another way is to triangulate the area using an algorithm called CDT "CONSTRAINED DELAUNAY TRIANGULATION" http://www.geom.uiuc.edu/~samuelp/del_project.html which creates the skeleton mesh. You then loop over traingles and extrude inwards at triangle points linking adjacent triangles together. You could also go with a hybrid here and create nodes at the triangles center rather than edges.
-
formerly hooligan2001 :)
He could just write something that places nodes 20 or 30 pixels apart like a tile system and removes nodes that are on top of objects. Then use a line of site sort of thing in the movement code to determine whether 2 points cross an object if not move to the next.
-
Please, Call Me Bob
When I give it a shot I'm going to split the field into convex polygons linking from all their open sides
Sounds similar to what malee suggested closer to the bottom of his post
And yes, was going to make nodes in the middle of each one
-
Senior Member
Originally Posted by artfabrique
perfectly selfexplanatory picture, thanks for posting!
edit: seems like others commenting here do not see a solution in this picture? I thought arrows would give it out
edit2: afterthought is telling me that there are multiple solutions, in fact, whole tree, if you turn arrows around every time there's an intersection... sounds like nice experiment to do some day.
Last edited by realMakc; 07-20-2010 at 01:58 PM.
-
I have a question on this subject. This guy is just doing A to B, which seems to be static for each level (being that on any given level it wont change until you are on the very next level). Now what if you have a movieclip (Enemy) who needs to path find to another movieclip (A character you move)? The path will always be changing as you move and there is no already solved answers that you could do..
(Sorry for the side question)
-
Pumpkin Carving 2008
It requires a bit of cheating on part of the AI. Baddie will have to anticipate where the hero will be and use that as a static reference point for path finding.
The 'Boose':
ASUS Sabertooth P67 TUF
Intel Core i7-2600K Quad-Core Sandy Bridge 3.4GHz Overclocked to 4.2GHz
8GB G.Skill Ripjaws 1600 DDR3
ASUS ENGTX550 TI DC/DI/1GD5 GeForce GTX 550 Ti (Fermi) 1GB 1GDDR5 (Overclocked to 1.1GHz)
New addition: OCZ Vertex 240GB SATA III SSD
WEI Score: 7.6
-
example
Lets say the baddie wonders around untill you are in its sight area.
When it sees you it chooses a path to that location, then then it moves a step toward you, it updates its path again (because you most likley moved), would this be a bad idea with 30 movie clips? or 30 baddies.. :\
-
Pumpkin Carving 2008
This might be relevant to the original discussion, but for a user-generated map, couldn't you apply a basic mesh and use some sort of flocking routine to force the nodes outside of any vectors?
The 'Boose':
ASUS Sabertooth P67 TUF
Intel Core i7-2600K Quad-Core Sandy Bridge 3.4GHz Overclocked to 4.2GHz
8GB G.Skill Ripjaws 1600 DDR3
ASUS ENGTX550 TI DC/DI/1GD5 GeForce GTX 550 Ti (Fermi) 1GB 1GDDR5 (Overclocked to 1.1GHz)
New addition: OCZ Vertex 240GB SATA III SSD
WEI Score: 7.6
-
Senior Member
You could only have the nearest baddie do the pathfinding routine, and then all nearby baddies follow him.
And even if you're moving, you wouldn't need to find the path again. You only need to find the path again once the player has moved to another node on the pathfinding mesh, and then the pathfinding can be divided over the next few frames.
Actually, to find the new path after the player has moved, you could start the pathfinding routine from the node that was picked last. Not only would this be much much faster, but it's almost more natural, that the AI is following the player.
Another optimization could be to leave traces on each node, and if a node has already been touched, then you just copy the rest of the path from that node that was already calculated, given that all your baddies are traveling towards the same target.
P.
WIP-ZOMBIES
I love vegetarians! More meat for the rest of us!
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|