Hello! Really really sorry for such a stupid questions and thus losing my 'face' here but I just need this cleared out. What's a 'node'? Specifically, I've heard of this term with regard to A*... To me it seems like some point on the map so that AI knows where it is? Am I right? Please help.

Are you expecting "Hahahahahahaha that ****Tard doesn't know what a node is hahahahahah."?

Nope.

GDers don't do that.

Don't ever be afraid to ask a question.

To answer yours, a node is just a unit.
Its a thing that connects to other nodes. It usually has a spot in the physical world.

From,
Nice coder

In addition to what Nice Coder has said, if you look at the bottom of this page, they show one example of a Node and what it stores in A*.

Ok, thanks a lot for both a reply and being kind unlike other forums... Thanks, I got it.

A* assumes that the map is something which is known in maths as a "graph". This is not a wiggly line drawn on a sheet of graph paper as you might imagine, but instead of set of "nodes" connected with things called "edges".

Think of it as a stick-and-ball model (like in Chemistry), where the nodes are the balls and the edges are the sticks.

Of course A* is usually used where the map is very regular, hence is a continuous (either square or hex) grid of nodes, each connected to 4 (or 6) of its neighbours by edges.

This is the most useful application of A*, beause it allows the heuristic to be calculated usefully and cheaply.

Mark

from what ive read this term applies to problem spaces outside of pathfinding aswell....... i think :S

Quote: From Wikipedia:
A node is a basic unit used to build data structures, such as linked lists and tree data structures. Nodes contain data and/or links to other nodes. Links between nodes are often implemented by pointers or references.

good old wiki :) it's example is better because it's not reffering to a specific lanauge (this A* thing or what ever it is)

(this description will allow you to visualize a node tree in your head)
A node is best visualized as a sphere, and this sphere can produce a "branch", a branch is best seen as a straight line.

Lets have 3 spheres, node A, node B.
( -> means to)
node A has a branch that attaches to node, A->B, this branch could also be seen as going B->A.

this in programming means that A has a variable that contains the location of point be (usualy a pointer to it or some way of naming and accessing B), this allows us to move from A to B.

If we want another node we creat that node and creat a branch to it from either A or B (having a branch from A and B to C is also possible)

lets show this with ASCII art :D


Step 1. no branch (most likely B was just created)

A     B

step 2. branch A->B

A---B

now A can see B and B can see A

step 3. creat C

A---B             C

step 4. branch B->C

A---B---C

now we can go from A to C if we go through B, but this may not be what we want so we make a branch to C from A, other wise to get to see we need to folow this path A->B->C.

step 5. branch from A->C

A----B\    / \  /  \/  C

We now have 3 "nodes" each node can hold what ever you wish, for a basic brute force AI I'm making I use tree nodes to keep track of clicks on a grid, each click is a node and contains the state of the graph it was in, each branch off of a node represents what happend when we made that click and what we can do, we then branch off of that node, and creat nodes attached to it the represetn possible clicks (this is described a bit better mabe worse in my collapse post).

A more classic "node" tree is a binary tree, each node spawns 2 nodes.

node 1 has 2 nodes

those 2 have 2 each

and so forth

usualy deciding where to go in this tree/what to create in this tree is done with a conditional check:

at node 1: if A > B put A in node 2, else put in node 3

rise and repeat :)

also imagining a tree fractal helps:
http://id.mind.net/~zona/mmts/geometrySection/fractals/tree/treeFractal.html

big post hope it wasn't to long.

Quote:
node A has a branch that attaches to node, A->B, this branch could also be seen as going B->A.

I'm going to be pedantic and say that this needn't be the case. It's not true that in every graph if A is attached to B then B is attached to A. A graph of this type is called a digraph where arrows along edges denote what is connected to what.

A real life example of this is the graph denoting "who can see who". A is behind a one way mirror with B in front of it. A can see B, but B cannot see A (B can see itself).

Quote: Original post by MDI
A real life example of this is the graph denoting "who can see who". A is behind a one way mirror with B in front of it. A can see B, but B cannot see A (B can see itself).

I'm a big fan of the "guy walking off a cliff" example of that =]