AI-Pathfinding-AStar-Rectangle

 view release on metacpan or  search on metacpan

Rectangle.xs  view on Meta::CPAN

#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

#include "ppport.h"


#define cxinc() Perl_cxinc(aTHX)
#define ARRAY_SIZE(x) (sizeof(x)/sizeof(x[0]))

#ifdef _MSC_VER
    #define inline 
#endif

inline bool is_hash(SV *x){
    return SvTYPE(x) == SVt_PVHV;
}

struct map_item{
    int g;
    int h;
    int k;
    char prev;
    char open;
    char closed;
    char reserved[1];
};
struct map_like{
    unsigned int width;
    unsigned int height;
    signed int start_x;
    signed int start_y;
    signed int current_x;
    signed int current_y;
    unsigned char map[];
};

#ifndef PERL_UNUSED_VAR
#  define PERL_UNUSED_VAR(var) if (0) var = var
#endif


#ifndef croak_xs_usage
#ifndef PERL_ARGS_ASSERT_CROAK_XS_USAGE
#define PERL_ARGS_ASSERT_CROAK_XS_USAGE assert(cv); assert(params)

/* prototype to pass -Wmissing-prototypes */
STATIC void
M_croak_xs_usage(pTHX_ const CV *const cv, const char *const params);

STATIC void
M_croak_xs_usage(pTHX_ const CV *const cv, const char *const params)
{
    const GV *const gv = CvGV(cv);

    PERL_ARGS_ASSERT_CROAK_XS_USAGE;

    if (gv) {
        const char *const gvname = GvNAME(gv);
        const HV *const stash = GvSTASH(gv);
        const char *const hvname = stash ? HvNAME(stash) : NULL;

        if (hvname)
            Perl_croak(aTHX_ "Usage: %s::%s(%s)", hvname, gvname, params);
        else
            Perl_croak(aTHX_ "Usage: %s(%s)", gvname, params);
    } else {
        /* Pants. I don't think that it should be possible to get here. */
        Perl_croak(aTHX_ "Usage: CODE(0x%"UVxf")(%s)", PTR2UV(cv), params);
    }
}
#endif
#ifdef PERL_IMPLICIT_CONTEXT
#define croak_xs_usage(a,b)     M_croak_xs_usage(aTHX_ a,b)
#else
#define croak_xs_usage          M_croak_xs_usage
#endif
#endif


#ifdef newXS_flags
#define newXSproto_portable(name, c_impl, file, proto) newXS_flags(name, c_impl, file, proto, 0)
#else
#define newXSproto_portable(name, c_impl, file, proto) (PL_Sv=(SV*)newXS(name, c_impl, file), sv_setpv(PL_Sv, proto), (CV*)PL_Sv)
#endif /* !defined(newXS_flags) */

Rectangle.xs  view on Meta::CPAN

            }
	    else {
		int index;
		int min_k; 
		index = opens_start;
		min_k = layout[opens[opens_start]].k ; // + layout[opens[opens_start]].h; 

		for (i = opens_start+1; i<opens_end; ++i){
		    int k = layout[opens[i]].k ; // + layout[opens[i]].h;
		    if (min_k> k){
			min_k = k;
			index = i;
		    }
		}
		current = opens[index];
		opens[index] = opens[opens_start];
		++opens_start;
		iter_num++;
	    }
        }

	{ 
	    STRLEN i;
	    SV* path;
	    U8 *path_pv;
	    STRLEN path_len;

	    path = sv_2mortal(newSVpvn("",0));

	    //
	    // 1

	    while(current != start_offset){
		STRLEN i = layout[current].prev;
		sv_catpvn_nomg(path, (char *) &path_char[i], (STRLEN) 1);
		current -= moves[i];
	    };
	    // 2
	    // 3
	    //
	    path_pv = (U8*)SvPV( path, path_len);
	    for(i=0; i<path_len/2; ++i){
		U8 x;
		x = path_pv[path_len-i-1];
		path_pv[path_len - i - 1] = path_pv[i];
		path_pv[ i ] = x;
	    }
	    if (GIMME_V == G_ARRAY){
		XPUSHs(path);
		XPUSHs(&PL_sv_yes);
	    }
	    else {
		XPUSHs(path);
	    }
	}

        free_allocated:;
        (void) Safefree(opens);
        (void) Safefree(layout);
        
        last_op:; // last resort Can't use return

void 
astar( self, from_x, from_y, to_x, to_y )
int from_x;
int from_y;
int to_x;
int to_y;
SV* self;
    INIT:
    pmap newmap;
    int moves[10];
    struct map_item *layout;
    int current, end_offset, start_offset;
    int *opens;
    int opens_start;
    int opens_end;
    static U8 path_char[8]={'8','1','2','3','4','9','6','7'};
    static int weigths[8]   ={10,14,10,14,10,14,10,14};
    int iter_num;
    int index;
    int map_size;
    PPCODE:
        if (!sv_isobject(self))
            croak("Need object");
        newmap = (pmap) SvPV_nolen(SvRV(self));
        if (!on_the_map(newmap, from_x, from_y) || !on_the_map(newmap, to_x, to_y)){
            XPUSHs(&PL_sv_no);
            goto last_op;
        }
        if (! newmap->map[get_offset(newmap, from_x, from_y)] 
            || ! newmap->map[get_offset(newmap, to_x, to_y)]){
            XPUSHs(&PL_sv_no);
            goto last_op;
        }

        
        start_offset = get_offset(newmap, from_x, from_y);
        end_offset = get_offset(newmap, to_x, to_y);

        if (start_offset == end_offset){
            XPUSHs(&PL_sv_no);
            XPUSHs(&PL_sv_yes);
            goto last_op;
        }

	map_size = (2+newmap->width) * (2+newmap->height);
        Newxz(layout, map_size, struct map_item);
        Newx(opens, map_size, int);

        init_move_offset(newmap, moves, 1);

        opens_start = 0;
        opens_end   = 0;

        iter_num = 0;
        current = start_offset;
        layout[current].g      = 0;

        while( current != end_offset){
            int i; 

Rectangle.xs  view on Meta::CPAN

                    int f = layout[opens[i]].g  + layout[opens[i]].h;
                    if (min_f> f){
                        min_f = f;
                        index = i;
                    }
                }

            }
            else {
                int min_k; 
                index = opens_start;
                min_k = layout[opens[opens_start]].k ; // + layout[opens[opens_start]].h; 

                for (i = opens_start+1; i<opens_end; ++i){
                    int k = layout[opens[i]].k ; // + layout[opens[i]].h;
                    if (min_k> k){
                        min_k = k;
                        index = i;
                    }
                }
            }
            current = opens[index];
            opens[index] = opens[opens_start];
            ++opens_start;
            iter_num++;
        }

	{ 
	    STRLEN i;
	    SV* path;
	    U8 *path_pv;
	    STRLEN path_len;

	    path = sv_2mortal(newSVpvn("",0));

	    while(current != start_offset){
		STRLEN i = layout[current].prev;
		sv_catpvn_nomg(path, (char *)&path_char[i], (STRLEN)1);
		current -= moves[i];
	    };
	    path_pv = (U8*)SvPV( path, path_len);
	    for(i=0; i<path_len/2; ++i){
		U8 x;
		x = path_pv[path_len-i-1];
		path_pv[path_len - i - 1] = path_pv[i];
		path_pv[ i ] = x;
	    }
	    if (GIMME_V == G_ARRAY){
		XPUSHs(path);
		XPUSHs(&PL_sv_yes);
	    }
	    else {
		XPUSHs(path);
	    }
	}

        free_allocated:;
        (void) Safefree(opens);
        (void) Safefree(layout);
        
        last_op:; // last resort Can't use return