Implementation - Terasology/TutorialPathfinding GitHub Wiki

This function deals with Implementation details of the Pathfinding System we have set up.

Walkable Blocks

Walkable Blocks are those blocks on which characters can walk on. More formally, these are blocks with at least two penetrable blocks above them (mostly air blocks).

    if (block.isPenetrable()) {
                        airMap[offset]++;
                    } else {
                        if (airMap[offset] >= 2) {
                            WalkableBlock walkableBlock = new WalkableBlock(blockPos.x, blockPos.z, blockPos.y);
                            map.cells[offset].addBlock(walkableBlock);
                            map.walkableBlocks.add(walkableBlock);
                        }
                       airMap[offset] = 0;
                    }

This is the relevant code that can be found in WalkableBlockFinder.java. Offset here represents the position of the block inside a NavGraphChunk. More on this later

Navgraph Chunk

The Terasology world is divided into various chunks each having dimensions of (16 x 32 x 16). A NavgraphChunk represents an actual chunk but contains pathfinding relevant information such as all the WalkableBlocks and floors it contains. Each NavGraphChunk is 2D array of NavGraphCells.

NavGraphCell

A NavGraphCell is the smallest entity that we deal with in terms of Pathfinding. It is essentially a list of all the WalkableBlocks at some x and z position.

Sweeps

Sweeps represent blocks that are lined next to each other without any holes or corners.

     if (leftNeighbor != null) {
                sweep = sweepMap.get(leftNeighbor);
            } else {
                sweep = new Sweep();
                sweeps.add(sweep);
            }

This comes from findSweeps() in FloorFinder.java. If the left neighbour of the current block is Walkable, (since we iterate from left to right and it has already been processed), we can just set the current block's sweep as the left neighbour's, otherwise, we create a new Sweep for this block and move on.

Regions

Each region represents a group of sweeps that are connected. When we find sweeps, we also add neighbours to the sweeps that can only come from the upNeighbours. Now we iterate over all the sweeps and all the blocks from neighbouring sweeps are mapped to a common region.

            for (Sweep sweep : sweeps) {
                if (sweep.neighbor != null && sweep.neighborCount == count.get(sweep.neighbor)) {
                    sweep.region = sweep.neighbor;
                } else {
                    sweep.region = new Region(regions.size());
                    regions.add(sweep.region);
                }
            }
            for (int x = 0; x < NavGraphChunk.SIZE_X; x++) {
                int offset = x + z * NavGraphChunk.SIZE_Z;
                NavGraphCell cell = map.cells[offset];

                for (WalkableBlock block : cell.blocks) {
                    Sweep sweep = sweepMap.remove(block);
                    Region region = sweep.region;
                    regionMap.put(block, region);
                    region.setPassable(block.x() - worldPos.x, block.z() - worldPos.z);
                }
            }

This comes from findRegions in FloorFinder.java . We iterate over all the sweeps and map the current sweeps region to the neighbours. Since we iterate from up to down, this cascades all the way up to the topmost neigbour. Thus, effectively mapping all the neighbouring sweeps to a common region.

Floors

Floors are groups of regions in our third level of abstraction for Hierarchical Pathfinding. They are basically regions which are merged if they are neighbouring to each other.

        for (Region region : regions) {
            if (region.floor != null) {
                continue;
            }
            Floor floor = new Floor(map, map.floors.size());
            map.floors.add(floor);

            List<Region> stack = Lists.newLinkedList();
            stack.add(0, region);

            while (!stack.isEmpty()) {
                Collections.sort(stack, new Comparator<Region>() {
                    @Override`
                    public int compare(Region o1, Region o2) {
                        return o1.id < o2.id ? -1 : o1.id > o2.id ? 1 : 0;
                    }
                });
                Region current = stack.remove(0);
                if (current.floor != null) {
                    continue;
                }
                if (!floor.overlap(current)) {
                    floor.merge(current);

                    Set<Region> neighborRegions = current.getNeighborRegions();
                    for (Region neighborRegion : neighborRegions) {
                        if (neighborRegion.floor == null) {
                            stack.add(neighborRegion);
                        }
                    }
                }
            }
        }

The stack has a custom comparator that sorts the regions in increasing order of ids. Thus current will be the region with the largest id.

Connecting Regions and floors.

The neighbour regions are calculated based on the border blocks, blocks whose neighbour blocks are of a different region. We iterate through all the cells once all the regions have been created, and find blocks that satisfy these conditions. Once they do, we mark the neigbouring blocks region as the current regions neighbour region.

    private void findRegionNeighbors(NavGraphCell cell) {
        for (WalkableBlock block : cell.blocks) {
            Region region = regionMap.get(block);
            if (region == null) {
                continue;
            }

            for (WalkableBlock neighbor : block.neighbors) {
                Region neighborRegion = regionMap.get(neighbor);
                if ((neighbor == null) || (neighborRegion != null && neighborRegion.id != region.id)) {
                    region.addNeighborBlock(block, neighbor, neighborRegion);
                }
            }
        }
    }