compression & path finding

compression & path finding

I.compression:
Run length Encoding
Huffman tress
 
II.path finding
 
1.Tile-based game
 random bounce method
 The Breadth-First Search
 add Heuristic (simple,complex way) to the Breadth-First Search
 The A* path finding
 
2.Line-based game
Quadtresss:In a large square game world,You split that up into four squares,Then you go to each squre and split it up into
another four squares.And you keep doing this over and over.This is called a quadtres.
Create a quadtree out of the map so that the tree is full to a certain numberof levels (3 or 4 is good). Now, for each quad
on the lowest level of the tree, check the midpoint of each quad. If all four of the quad’s midpoints are not bstructed,then
you can remove that branch of the tree. When the lowest level is complete, go up to the next level and continue removing
nodes, but only if all four branches of each node go down to the same level.
wayPoint:Each of the points on the graph is called a waypoint.
 
3.Here is the tilemap pathfinding algorithm:

TilePathfind( map, start, goal )
Queue q
q.Enqueue( start )
while( q is not empty )
current = q.Front
q.Dequeue
Mark( current )
for( all 8 directions )
if( adjacent node not marked )
q.Enqueue( adjacent node )
adjacent node.previous = current
end if
end for
end while
end Function

 

Now, to adapt this algorithm to linked graphs, you just need to change one thing.
Change this:
for( all 8 directions )
To this:
for( each linked node )
And the algorithms fit perfectly.
 

One thought on “compression & path finding

Leave a Reply

Your email address will not be published. Required fields are marked *