Nodes...

Wacov

I found out a bit about AI coding, and the simplest way to get effective pathfinding seems to be using nodes (waypoints)... I was wondering whether it's theoretically possible to do this using onTouch fields? If there was a way to find the closest node to the character, you'd then be able to search for a route through the nodes... if each one was affiliated with 1 or more other nodes, in direct line of sight, and it 'remembered' which nodes it had previously pased through en route, you'd then be able to stop each routefinding run when:

There are no available nodes to move onto
There are no nodes, except ones which have already been used, to pass onto
Finally, when a route ending in the target node is found, 'save' it, and end that run. Once all possible routes have been calculated, the character would follow the one that passes through the least number of nodes.

Firstly, I obviously don't know how to make this happen... it's all sort of theoretical. Moving between nodes is relatively easy, you just use a system based around lookAt, and even running through a list of nodes wouldn't be too much of a problem. I just can't get my head around the route calculation... there are also other problems, like how the choice of route would be made. Using the number of nodes isn't ideal, what'd be better is finding the distance the route takes. If anyone (Chris ) can help with the technicalities, it'd be appreciated.

Sgt.A.Johnson

I think I get it but I have no idea how to do it. Seems like a nice idea. What I'm trying to do at moment is make AI enemies for an FPS. Best I've come up with is flying things that avoid obstacles and shoot at you when you enter the room. Got it worked out its just not very interesting. I also might of worked out how to do deaths on it.

BTM

http://code.google.com/apis/sketchup/docs/ourdoc/tool.html

... Maybe you could find something there.

Wacov

I've done some more research, and what's needed is the A* algorithm... it's more effective, because it doesn't have to search every possible route, and helps with a couple of the technicalities... but the problem then is estimating the distance to the target. I also don't know how to compile lists using ruby script, or how to find the 'cost' of moving from one node to another... you'd really need to calculate the distance from the parent to the open node, which is either hard or impossible in SP. Search AI pathfinding on google to find tutorials etc...

Wacov

Ok, found out about arrays (lists), classes and attributes. Should all be useful... I'll try and make a route-following demo, where an object runs through a list of nodes to get to the target.

Update: Managed to get a system that finds the current position of an object working. Have a look at: http://sketchup.google.com/3dwarehouse/details?mid=fcb65ad19dd115f36cd8ad826e9017b8&prevstart=0 , it uses bits of my own knowledge and a bit of help from Chris's Knight demo

BTM

How did you find out what $curEvalGroup and attr_accessor were?

... Anyways, I might try my own similar system, with what I know.

Oh, and a way to see the actual position of it, when you click the spacebar

if key("space")==1 UI.messagebox @@player.pos.to_s ;end;

... You probably already knew how to do that though.

Wacov

$curEvalGroup, Chris told me about... I figured out how to find the position from what was in the Knight demo's script (the part that finds the speed). The other stuff, I found out from finally completing the 'Try Ruby' tutorial

This is really just getting all the pieces together for a pathfinding system... one important thing will be finding the nearest node, and, to add a mobile target, finding the nearest node to that...

BTM

http://code.google.com/apis/sketchup/docs/ourdoc/array.html#distance
... I don't know if you could implement it with sketchyphysics and/ or groups though. It seems to only be able to find the distance between 2 points, a point and a line, or a point and a face.

BTM

... Nevermind, I see you've found a workaround!

Wacov

UPDATE: YES! Thank you BTM!! It's accurate now, thanks to that lovely little code from Google. I'm gonna make a request to build the getPosition method into SP for the next release; until then, the code is:

def getPosition
return $curEvalGroup.transformation.origin
end

This can be entered anywhere, and will affect the entire model. Once entered, typing getPosition into any formula field will find the selected group's position, relative to the model's origin. To get just, say, the Red axes, use:

red=getPosition
red=red[0]

The [0] finds the first number in the 'list' of coordinates. Use [1] for the Green axes, and [2] for Blue.

BTM

See? As I mentioned earlier, there are other useful methods and classes available for use you can find in the SketchUp ruby API; Just go to http://code.google.com/apis/sketchup/docs/ourdoc/tool.html

CPhillips

Wacov I saw the code in the latest version and I think it is a little more complicated than it needs to be.

I dont think you need the class at all. Just store the position in the variables directly.

@SpherePos=getPosition()

Also there is a simpler way to get the distance between two points.

distance=@SpherePos.distance(@BoxPos)

Wacov

The classes aren't needed... I knew that from the start. It really begun with me testing whether classes worked in SP, then trying out storing information in the attributes... that works, so I can carry on with my little project ... The demo itself is basicallly a side product of me looking into slightly more advanced ruby.

The short way was the first way I tried; it didn't work. Even when classes aren't used, it won't allow it...?

Ok... I think the pathfinding is possible. It's gonna be complicated, maybe to the point where I can't realisticly use it, but here goes:

Step 1) Define a node as a target

Step 2) Determine the nearest node to the AI's current position (Add to the closed list, define as beginning of path)

Step 3) Find all nodes connected to the first. Add them to the open list, define the start as their respective parents

Step 4) Find the node on the open list with the lowest F cost (Distance along path from start + distance to target). Add this node to the closed list.

Step 5) Find all nodes connected to this one. Add them (Excluding those already on the closed list) to the open list, define this node as their parent

Step 6) Find the new lowest F cost open node. Add to the closed list, and continue...

Step 7) Once the target node is added to the closed list, you need to find the path. This is a simple matter of 'follow the parent', tracing back from the target to the start. Compile these nodes into a list, reverse it, and you're ready to go.

This can all be done in a single frame of the simulation... you can detect a change in the target by creating a 'lastTarget' variable at the end of every frame's script. If the target changes, just run the pathfinding again... this allows tracking of changing objectives. Finally, you could track a moving target by finding the nearest node to it, then chasing the target itself once you've 'caught up'.

All this would be supported by the node variable framework. Each node would constantly be updating its respective global variable, with its distance from the target, the list of connected nodes, and, if applicable, its parent node.

Oh, and Chris, I just had a peek at the SP3 ControllerCommands... you've added the ability to find the position AND the animation method you used into SP's code Why don't you tell us about this stuff?

CPhillips

Because they are only in SP3x and not RC1. If you use those functions it will only work with SP3x models.

There is a Python A* implimentation here:
http://arainyday.se/projects/python/AStar/

Python is pretty similar to ruby.

This project would probably be easier with the new scripting framework. You may want to wait and tackle this when it comes out.

Wacov

Ok, I've downloaded the latest versions of Python, PYGame, and something to extract the .gz. I found the folder, double-clicked on the python files, and nothing. How do I run the example?

Oh, and here's a basic path FOLLOWER. It can't avoid collisions, but it runs through the given list of nodes. It shows that:

A) It's possible to run a route based on a list
B) It's possible to create the node framework required for pathfinding
C) It could be relatively easy to set up the nodes. My system only requires you to give each node a unique number as an entity name; the script does the rest.

If you want to use the system, go ahead. The script's all in place... you have to include the stuff in the floor and pointer cone's onTick. You can copy the nodes fine, just give every copy a unique number as a name. Anyway, here's the link: http://sketchup.google.com/3dwarehouse/details?mid=6a0e83aefa4869dc6cd8ad826e9017b8

CPhillips

I didnt try to run it, I was just pointing it out as a resource. The .PY files are where the code is and they are just text.

CPhillips

Wacov your path finding model is amazing. I never would have thought that possible.

Wacov

Thanks! That's basically the system I'll use once the pathfinding has run. I've found a way to use attributes with the Hash variable system I'm using at the moment... it could either be:

@@n.attr[1]

Or:

@@n[1].attr

The first one invloves assigning attributes to the main variable, and setting them as hashes; the second means assigning attributes to the Fixnum class, which is less dynamic, and, I think, a bit strange.