An idea I thought I'd put up for grabs, something I thought of many moons ago.
A LinkedList structure with six possible branches from each node, representing positive and negative XYZ.

This mapping system would be applied to objects in the world. These nodes would represent a system of lines forming shortest routes, in turn these could be applied to AI for pathfinding, or simply to find the nearest objects for weighted need calculus.

The original idea from my youth was to keep three axial binary trees,but a hextree puts it all in one neat neural network.

Any thoughts?
Posted on 2002-12-01 09:23:32 by Homer
No feedback? Perhaps I should elucidate...

For any object in the 3d world, we can decide which is the next object in the X+,X-,Y+,Y-,Z+ and Z- directions.
That means, on its right,left,above,below,in front and behind.
Only one object can exist in one place, so is anyone interested in coding a solution to a sorting algorithm? It's not very difficult !!
Posted on 2002-12-02 09:37:37 by Homer
yes, it's a good idea but time constrains me to do something about it :) - but I'll code something if time permits.

Anyway, how would you like the sorting algo works on x? y? z? or make an algo for all directions?

A sideview of a world, since we are so cheap on creating a 3d one ;) :


xxxxxxxxx[ 2]xxxxxxxxxxxxx
xxxxxxxxx[ 1]xxxxxxxxxxxxx
xxxxxxxxx[ 0]xxxxxxxxxxxxx
[color=blue]xxxxxxxxx[-1]xxxxxxxxxxxxx[/color]
xxxxxxxxx[-2]xxxxxxxxxxxxx
[ 0] is on (x = 0, y = 0, z = 0)

assuming 2, 1, 0, -1, -2, shows a direction on y and everything on the horizontal on z. If we are going to sort a node, let's say:

-1(x = 0, y = -1, z = 0) and we want to sort all nodes on the z direction, then we are only going to sort all nodes on that level(the colored blue ones.)

This is how you want the sorting to behave? :)
Posted on 2002-12-03 23:13:27 by stryker
This is the first version. What it does are:

1. Add nodes to any direction at any node. (x+, x-, y+, y-, z+, z-)

2. Deallocate all nodes.

I've never tested extensively the deallocation routine but it seems to be working. I'm sure there will be bugs depending on the model of the hex tree but I have no time to test it fully. :)

So here it is...

I'll add sorting later. :)
[size=9].686

.MODEL FLAT, STDCALL
OPTION SCOPED
OPTION CASEMAP:NONE

INCLUDE C:\dev\masm32\include\windows.inc
INCLUDE C:\dev\masm32\include\kernel32.inc
INCLUDELIB C:\dev\masm32\lib\kernel32.lib
INCLUDE C:\dev\masm32\include\user32.inc
INCLUDELIB C:\dev\masm32\lib\user32.lib
INCLUDE C:\dev\masm32\include\masm32.inc
INCLUDELIB C:\dev\masm32\lib\masm32.lib

@str MACRO _str:VARARG
LOCAL @@1
IF @InStr(1, <_str>, <!">)
.DATA
@@1 DB _str, 0
.CODE
EXITM <OFFSET @@1>
ELSE
EXITM <_str>
ENDIF
ENDM

;by stryker

xcall MACRO function:REQ, parameters:VARARG
LOCAL psize, paddr, plen
IFNB <parameters>
psize = 0
FOR param, <parameters>
psize = psize + 4
ENDM
IF psize EQ 4
push parameters
ELSE
sub esp, psize
psize = 0
FOR param, <parameters>
IF @SizeStr(<param> ) GT 4
paddr SUBSTR <param>, 1, 5
IFIDNI paddr, <ADDR >
paddr SUBSTR <param>, 6, @SizeStr(<param>) - 5
lea eax, paddr
mov DWORD PTR [esp+psize*4], eax
ELSE
mov DWORD PTR [esp+psize*4], @str(<param>)
ENDIF
ELSE
mov DWORD PTR [esp+psize*4], @str(<param>)
ENDIF
psize = psize + 1
ENDM
ENDIF
ENDIF
call function
ENDM

hext struct
object DD ?
visited DD ?
xp DD ?
xm DD ?
yp DD ?
ym DD ?
zp DD ?
zm DD ?
hext ends

.CONST

;Direction Constants
;
;Postfix:
; P - Positive(+)
; M - Negative(-)

DXP EQU 0
DXM EQU 1
DYP EQU 2
DYM EQU 3
DZP EQU 4
DZM EQU 5

;Object Constants

NO_OBJECT EQU 0
SILVER_COIN EQU 1
ANKH EQU 2
SUN_STONE EQU 3
PRISMATIC_NECKLACE EQU 4
TWIG EQU 5

.DATA

addtable DD __from_xp, __from_xm, __from_yp, __from_ym, __from_zp, __from_zm

.DATA?

hHeap DD ?
basenode DD ?
buffer DB 8 DUP(?)

.CODE

;Procedure: addnode
;Requires: hHeap, the handle to the heap
; : a tree must have at least 1 node existing
;Parameters: node
; : object
; : direction, where the object is to be placed based on the position of the node parameter

addnode:

invoke HeapAlloc, hHeap, HEAP_ZERO_MEMORY, SIZEOF hext

;Place the object on the new node

mov edx, [esp+8]
mov (hext ptr [eax]).object, edx

;Connect the 2 nodes by determining the given direction

mov ecx, [esp+12]
mov edx, [esp+4]
jmp DWORD PTR [addtable+ecx*4]

__from_xp:

mov (hext ptr [edx]).xp, eax
mov (hext ptr [eax]).xm, edx
jmp __finished_adding_node

__from_xm:

mov (hext ptr [edx]).xm, eax
mov (hext ptr [eax]).xp, edx
jmp __finished_adding_node

__from_yp:

mov (hext ptr [edx]).yp, eax
mov (hext ptr [eax]).ym, edx
jmp __finished_adding_node

__from_ym:

mov (hext ptr [edx]).ym, eax
mov (hext ptr [eax]).yp, edx
jmp __finished_adding_node

__from_zp:

mov (hext ptr [edx]).zp, eax
mov (hext ptr [eax]).zm, edx
jmp __finished_adding_node

__from_zm:

mov (hext ptr [edx]).zm, eax
mov (hext ptr [eax]).zp, edx

__finished_adding_node:

retn 12

;Procedure: delallnode
;Requires: hHeap, the handle to the heap
;Parameters: node, pointer to a node - preferably the base node

delallnode:

mov eax, [esp+4]
test eax, eax
jz __exit_deallocation
cmp (hext ptr [eax]).visited, 0
jne __exit_deallocation
mov (hext ptr [eax]).visited, 1

;Traverse x+

push eax
mov eax, (hext ptr [eax]).xp
push eax
call delallnode
pop eax

;Traverse y+

push eax
mov eax, (hext ptr [eax]).yp
push eax
call delallnode
pop eax

;Traverse z+

push eax
mov eax, (hext ptr [eax]).zp
push eax
call delallnode
pop eax

;Traverse x-

push eax
mov eax, (hext ptr [eax]).xm
push eax
call delallnode
pop eax

;Traverse y-

push eax
mov eax, (hext ptr [eax]).ym
push eax
call delallnode
pop eax

;Traverse z-

push eax
mov eax, (hext ptr [eax]).zm
push eax
call delallnode
pop eax

;NULLify all nodes that are pointing on a node specified by EAX

mov edx, (hext ptr [eax]).xp
test edx, edx
jz @f
mov (hext ptr [edx]).xm, NULL
@@:
mov edx, (hext ptr [eax]).xm
test edx, edx
jz @f
mov (hext ptr [edx]).xp, NULL
@@:
mov edx, (hext ptr [eax]).yp
test edx, edx
jz @f
mov (hext ptr [edx]).ym, NULL
@@:
mov edx, (hext ptr [eax]).ym
test edx, edx
jz @f
mov (hext ptr [edx]).yp, NULL
@@:
mov edx, (hext ptr [eax]).zp
test edx, edx
jz @f
mov (hext ptr [edx]).zm, NULL
@@:
mov edx, (hext ptr [eax]).zm
test edx, edx
jz @f
mov (hext ptr [edx]).zp, NULL
@@:

pushad
invoke MessageBox, 0, 0, 0, 0
popad

invoke HeapFree, hHeap, NULL, eax

__exit_deallocation:

retn 4

start:

;Create scene

invoke GetProcessHeap
mov hHeap, eax

;Create base node/root node

invoke HeapAlloc, eax, HEAP_ZERO_MEMORY, SIZEOF hext
mov basenode, eax

xcall addnode, eax, NO_OBJECT, DZM
mov eax, basenode
xcall addnode, eax, SUN_STONE, DYP

;mov eax, basenode
;mov eax, (hext ptr [eax]).zm
;mov eax, (hext ptr [eax]).object
;invoke dwtoa, eax, OFFSET buffer
;invoke MessageBox, 0, OFFSET buffer, 0, 0

;mov eax, basenode
;mov eax, (hext ptr [eax]).yp
;mov eax, (hext ptr [eax]).object
;invoke dwtoa, eax, OFFSET buffer
;invoke MessageBox, 0, OFFSET buffer, 0, 0

xcall delallnode, basenode

invoke ExitProcess, 0

end start[/size]
as you can see here the scene looks like this.

from the base node(0, 0, 0) going (0, 0, -1) - this node has no object in it.

again from the base node going (0, 1, 0) we place a SUN_STONE object. :)

I'll add more explanations later.

If you see this code
pushad

invoke MessageBox, 0, 0, 0, 0
popad
I use this snippet to test how many nodes we deallocated. Based on this example it's 3...

BTW, I use this kind of coordinate. :)
Posted on 2002-12-05 13:57:14 by stryker
there are still a lot to be done and I still haven't finished connecting all nodes... Hex Tree is so complex to implement because you have to think of all adjacent nodes.

at the addnode procedure, there are still some codes missing but I didn't add it, because it will be too complex to understand the whole idea of a hextree.

the .visited field of our structure is very important during deallocation.

Anywho, it's a start. :)
Posted on 2002-12-05 14:10:41 by stryker
nice stuff ! good start :)

What I would like to point out is that your nodes are not equipped to hold more than one object - you are treating the nodes as representative of space !!
This means you can have empty nodes contianing no object...


What I was suggesting initially was not a nodemap of the world space per se, simply a network between the actual objects within the world.
I was planning on keeping a second nodemap of world space.
I prefer your system !!
This can be better used for pathfinding, although it's less suitable for weighted need calculus, it's still admirable.

Have you seen my work on LinkedLists?
Under that system, we already have 4x links, meaning we have to supply 2 more.
A Node might look like this:

MyNode STRUCT
LO LinkedObject <> ;contains support for node name, x and y links
LOType DWORD WORLDNODE ;Tag the structure type (see below)
zPrev LPLINKEDOBJECT ? ;pointers for the missing axis
zNext LPLINKEDOBJECT ?
vPos D3DVECTOR3 <> ;3D position of this node exactly
fRadius FLOAT ? ;Radius of this node can be used for ambient sound fx
pSound LPCACHEDOBJECT ?;pointer to a loaded and cached object...ambientsfx
pObjectList LPLINKEDOBJECT ? ;pointer to first of a linkedlist of close objects
MyNode ENDS

This type of Spatial Node is more advanced.
It can be named, supports a centre and radius in 3d space which can be used to create overlapping regional ambient sound effects, and contains a member representing the Head of a LinkedList of proximate objects in this worldspace.
These are the objects "owned" by this Node.
Furthermore, among the LinkedList of world objects in this spherical region of space, may exist one or more Nested Nodes !!! (That's why I have begun tagging my LO structures - so you can mix different LinkedObjects in a single LinkedList).
This means that a larger region can house smaller regions of space - for example, we might wish to have one ambient sound for when we enter the house and another sound to be heard in the bedroom (radio) or in the cellar (weird creaking) but without losing the ambient house sound...
It also fixes the poor support for multiple proximate objects in a NodeSpace.
This I think might prove to be a better blend for use in terms of both AI pathfinding through tighter networks, and also in terms of faster identification of grouped static objects for weighted need calculus.
Keep up the good work !!
Posted on 2002-12-08 07:54:28 by Homer
I haven't seen the code on your LL but I'll take a look at it. I'm just skimming some parts of your post up here. I'll reread them some other time, if I get to continue on working on this. :)

I'll also consider what you meant above.

:alright:
Posted on 2002-12-08 23:16:49 by stryker
The actual Sorting algo doesn't need to be complex...
consider this:

how many nodes do we need for starters? one per object...
we create N nodes.
Now we begin to "sort" them.
No actual sorting is done, we are about to create the seemingly complex links between the nodes...

Loop for all objects:
For each object: which OTHER object has the next highest value in X?
which has the next lowest value in X?
in Y?
in Z?

We begin to create links between the nodes.
They can loop, thats ok !! They can be nets.
This network of nodes does not yet take spatial nodes into account.
They will be inserted in a separate phase.
(my LL code provides for easy insertion)

That seems fairly simple! It relies on us having a well-defined node structure...
Posted on 2002-12-08 23:43:54 by Homer
If anyone is interested, I'll share a method of pathfinding for AI using networked spacenodes which uses a static lookup table for extremely fast pathfinding.
It requires N^2 dwords where N=#nodes...
Posted on 2002-12-08 23:48:34 by Homer
Sounds nice :) I'd like to have a look...

Sliver
Posted on 2002-12-12 19:10:52 by Sliver
Yep, I'm interested
Posted on 2002-12-12 19:36:12 by Maelstrom
ok this guy here has the right idea Check This Out

He is describing the pathfinding table in simplistic spatial terms.
The system I'd like to implement is much enhanced but that document gives a good indication of what the hell I'm talking about.
It needs to have nodes for static world objects incorprated into it.
This would allow our AI NPC to locate nearby goodies which will bear weight on the outcome of the NPC's goal-oriented motion.
Note that much of the table is empty.

It's occurred to me that there's a much better way to do this, and in some ways it's similar to a portal engine and in others similar to John Carmack's "bsp2 - PVS" (potentially-visible sets)...I'll try to describe it.

For starters imagine we have built a 3d world. We will place imaginary markers at key locations throughout the world, which are stored as an array of vertices. Added to this array are the locations of any desirable objects as more vertices.
I'm not going into "Need-weighting", I'll keep this simple.
These important locations are marker nodes which the AI will use...
what we will do is build a network of links between the nodes. This won't be cheap, but can be done in a pre-game processing phase as follows:
(assuming that the 3d world is loaded into memory)
Beginning with any arbitrary node (the first vertex in the array), we will perform a line-of-sight test against every other node (the rest of the array). If the line of sight is not obstructed, we create a link from the current node to the next node.
Importantly, we also note the ray length (difference between vertex values) which is considered THE WEIGHTING FOR THAT LINK. This saves us from calculating distances in realtime (everything counts).
If the line of sight between any two nodes is obstructed, we mark this link as ILLEGAL which saves the comparison being made betwen these two vertices for the remainder of the processing phase (see below).
When the vertex array has been completely processed with respect to the initial vertex comparisons loop, we repeat the process, performing line of sight tests for each of the nodemarker vertices against all the others EXCEPT any marked as "illegal".
We now have a weighted neural network !!

Importantly, we would not be using LinkedList-style linking of nodes, rather we would use the above algorithm to generate a lookup-table which works just like the ones described in the document Here
This LookupTable could be a dynamic array, we don't need the dead wood.
Any thoughts?
Posted on 2002-12-13 02:33:47 by Homer