• Advertisement
Sign in to follow this  

What's a 'node'?

This topic is 4704 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
Ok, thanks a lot for both a reply and being kind unlike other forums... Thanks, I got it.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
from what ive read this term applies to problem spaces outside of pathfinding aswell....... i think :S

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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 =]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster


Genericly, a node is a symbolic object type which can be used to manipulate a data set (ie- 'nodes' are used in trees and link lists).

To use A* you divide up your map into 'tiles' or 'regions' in order to search out a 'good' path. You use node objects that correspond 1 to 1 with your subdivisions
and define relations between them to create a data network. You perform your algorithm upon this network using knowledge about the relations (ie- like the adjacency of cartesian base tiles).

Often because the path search is done frequently and is a significant user of CPU resources, the node functinality is imbedded into the base map data structures
to lower the setup overhead of building the 'node' network.


An frequently used optomization of A* is to make 2 levels of hierarchy -- the low 'tile' level amd a higher 'region'/'area' level. By searching out a generalized path first (on a much smaller network) and then only having to do shorter (within 'area' - subset) low level pathfind, ALOT less processing is needed (CPU requirements to search networks usually grow geometricly with node count.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement