//
// Copyright(C) 1993-1996 Id Software, Inc.
// Copyright(C) 1999 id Software, Chi Hoang, Lee Killough, Jim Flynn, Rand Phares, Ty Halderman
// Copyright(C) 2005-2014 Simon Howard
// Copyright(C) 2017 Fabian Greffrath
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// DESCRIPTION:
//	[crispy] Create Blockmap
//

#include <stdlib.h>
#include "h2def.h"
#include "p_local.h"
#include "i_system.h"
#include "m_fixed.h"
#include "z_zone.h"

// [crispy] taken from mbfsrc/P_SETUP.C:547-707, slightly adapted

void P_CreateBlockMap(void)
{
    register int i;
    fixed_t minx = INT_MAX, miny = INT_MAX, maxx = INT_MIN, maxy = INT_MIN;

    // First find limits of map

    for (i = 0; i < numvertexes; i++)
    {
        if (vertexes[i].x >> FRACBITS < minx)
            minx = vertexes[i].x >> FRACBITS;
        else if (vertexes[i].x >> FRACBITS > maxx)
            maxx = vertexes[i].x >> FRACBITS;
        if (vertexes[i].y >> FRACBITS < miny)
            miny = vertexes[i].y >> FRACBITS;
        else if (vertexes[i].y >> FRACBITS > maxy)
            maxy = vertexes[i].y >> FRACBITS;
    }

#if 0
  // [crispy] doombsp/DRAWING.M:175-178
  minx -= 8; miny -= 8;
  maxx += 8; maxy += 8;
#endif

    // Save blockmap parameters

    bmaporgx = minx << FRACBITS;
    bmaporgy = miny << FRACBITS;
    bmapwidth = ((maxx - minx) >> MAPBTOFRAC) + 1;
    bmapheight = ((maxy - miny) >> MAPBTOFRAC) + 1;

    // Compute blockmap, which is stored as a 2d array of variable-sized lists.
    //
    // Pseudocode:
    //
    // For each linedef:
    //
    //   Map the starting and ending vertices to blocks.
    //
    //   Starting in the starting vertex's block, do:
    //
    //     Add linedef to current block's list, dynamically resizing it.
    //
    //     If current block is the same as the ending vertex's block, exit loop.
    //
    //     Move to an adjacent block by moving towards the ending block in
    //     either the x or y direction, to the block which contains the linedef.

    {
        typedef struct
        {
            int n, nalloc, *list;
        } bmap_t;                                 // blocklist structure
        unsigned tot = bmapwidth * bmapheight;    // size of blockmap
        bmap_t *bmap = calloc(sizeof *bmap, tot); // array of blocklists
        int x, y, adx, ady, bend;

        for (i = 0; i < numlines; i++)
        {
            int dx, dy, diff, b;

            // starting coordinates
            x = (lines[i].v1->x >> FRACBITS) - minx;
            y = (lines[i].v1->y >> FRACBITS) - miny;

            // x-y deltas
            adx = lines[i].dx >> FRACBITS;
            ady = lines[i].dy >> FRACBITS;
            dx = adx < 0 ? -1 : 1;
            dy = ady < 0 ? -1 : 1;

            // difference in preferring to move across y (>0) instead of x (<0)
            if (!adx)
            {
                diff = 1;
            }
            else if (!ady)
            {
                diff = -1;
            }
            else
            {
                diff = (((x >> MAPBTOFRAC) << MAPBTOFRAC) +
                        (dx > 0 ? MAPBLOCKUNITS - 1 : 0) - x) *
                           (ady = abs(ady)) * dx -
                       (((y >> MAPBTOFRAC) << MAPBTOFRAC) +
                        (dy > 0 ? MAPBLOCKUNITS - 1 : 0) - y) *
                           (adx = abs(adx)) * dy;
            }

            // starting block, and pointer to its blocklist structure
            b = (y >> MAPBTOFRAC) * bmapwidth + (x >> MAPBTOFRAC);

            // ending block
            bend = (((lines[i].v2->y >> FRACBITS) - miny) >> MAPBTOFRAC) *
                       bmapwidth +
                   (((lines[i].v2->x >> FRACBITS) - minx) >> MAPBTOFRAC);

            // delta for pointer when moving across y
            dy *= bmapwidth;

            // deltas for diff inside the loop
            adx <<= MAPBTOFRAC;
            ady <<= MAPBTOFRAC;

            // Now we simply iterate block-by-block until we reach the end block.
            while ((unsigned) b < tot) // failsafe -- should ALWAYS be true
            {
                // Increase size of allocated list if necessary
                if (bmap[b].n >= bmap[b].nalloc)
                {
                    bmap[b].nalloc = bmap[b].nalloc ? bmap[b].nalloc * 2 : 8;
                    bmap[b].list = I_Realloc(
                        bmap[b].list, bmap[b].nalloc * sizeof(*bmap->list));
                }

                // Add linedef to end of list
                bmap[b].list[bmap[b].n++] = i;

                // If we have reached the last block, exit
                if (b == bend)
                    break;

                // Move in either the x or y direction to the next block
                if (diff < 0)
                {
                    diff += ady;
                    b += dx;
                }
                else
                {
                    diff -= adx;
                    b += dy;
                }
            }
        }

        // Compute the total size of the blockmap.
        //
        // Compression of empty blocks is performed by reserving two offset words
        // at tot and tot+1.
        //
        // 4 words, unused if this routine is called, are reserved at the start.

        {
            // we need at least 1 word per block, plus reserved's
            int count = tot + 6;

            for (i = 0; i < tot; i++)
                if (bmap[i].n)
                    // 1 header word + 1 trailer word + blocklist
                    count += bmap[i].n + 2;

            // Allocate blockmap lump with computed count
            blockmaplump = Z_Malloc(sizeof(*blockmaplump) * count, PU_LEVEL, 0);
        }

        // Now compress the blockmap.
        {
            int ndx = tot += 4; // Advance index to start of linedef lists
            bmap_t *bp = bmap;  // Start of uncompressed blockmap

            blockmaplump[ndx++] = 0;  // Store an empty blockmap list at start
            blockmaplump[ndx++] = -1; // (Used for compression)

            for (i = 4; i < tot; i++, bp++)
            {
                if (bp->n) // Non-empty blocklist
                {
                    // Store index & header
                    blockmaplump[blockmaplump[i] = ndx++] = 0;
                    do
                    {
                        // Copy linedef list
                        blockmaplump[ndx++] = bp->list[--bp->n];
                    } while (bp->n);
                    blockmaplump[ndx++] = -1; // Store trailer
                    free(bp->list);           // Free linedef list
                }
                else
                {
                    // Empty blocklist: point to reserved empty blocklist
                    blockmaplump[i] = tot;
                }
            }

            free(bmap); // Free uncompressed blockmap
        }
    }

    // [crispy] copied over from P_LoadBlockMap()
    {
        int count = sizeof(*blocklinks) * bmapwidth * bmapheight;
        blocklinks = Z_Malloc(count, PU_LEVEL, 0);
        memset(blocklinks, 0, count);
        blockmap = blockmaplump + 4;
    }

    fprintf(stderr, "P_CreateBlockMap: BLOCKMAP recreated.\n");
}
