aboutsummaryrefslogtreecommitdiff
path: root/modules/mod_path/mod_path.c
diff options
context:
space:
mode:
Diffstat (limited to 'modules/mod_path/mod_path.c')
-rw-r--r--modules/mod_path/mod_path.c395
1 files changed, 395 insertions, 0 deletions
diff --git a/modules/mod_path/mod_path.c b/modules/mod_path/mod_path.c
new file mode 100644
index 0000000..ded80f6
--- /dev/null
+++ b/modules/mod_path/mod_path.c
@@ -0,0 +1,395 @@
+/*
+ * Copyright © 2006-2016 SplinterGU (Fenix/Bennugd)
+ * Copyright © 2002-2006 Fenix Team (Fenix)
+ * Copyright © 1999-2002 José Luis Cebrián Pagüe (Fenix)
+ *
+ * This file is part of Bennu - Game Development
+ *
+ * This software is provided 'as-is', without any express or implied
+ * warranty. In no event will the authors be held liable for any damages
+ * arising from the use of this software.
+ *
+ * Permission is granted to anyone to use this software for any purpose,
+ * including commercial applications, and to alter it and redistribute it
+ * freely, subject to the following restrictions:
+ *
+ * 1. The origin of this software must not be misrepresented; you must not
+ * claim that you wrote the original software. If you use this software
+ * in a product, an acknowledgment in the product documentation would be
+ * appreciated but is not required.
+ *
+ * 2. Altered source versions must be plainly marked as such, and must not be
+ * misrepresented as being the original software.
+ *
+ * 3. This notice may not be removed or altered from any source
+ * distribution.
+ *
+ */
+
+/* --------------------------------------------------------------------------- */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "bgddl.h"
+#include "bgdrtm.h"
+
+#include "libgrbase.h"
+
+/* --------------------------------------------------------------------------- */
+
+#include "mod_path.h"
+
+/* --------------------------------------------------------------------------- */
+
+typedef struct _node
+{
+ unsigned int x, y ;
+ double f, g, h ;
+ struct _node * parent ;
+ struct _node * next ;
+ struct _node * inext ;
+}
+node ;
+
+/* --------------------------------------------------------------------------- */
+
+static int * path_result = NULL ;
+static int * path_result_pointer = NULL ;
+
+static node * pf_all = NULL;
+
+static node * pf_open = NULL ;
+static node * pf_closed = NULL ;
+static node * found = NULL ;
+
+static int destination_x, destination_y ;
+static int startup_x, startup_y ;
+
+static GRAPH * map ;
+
+static int block_if = 1 ;
+
+/* --------------------------------------------------------------------------- */
+
+static double heuristic( int x, int y )
+{
+ int dx, dy ;
+ uint8_t block = (( uint8_t* )map->data )[map->pitch*y+x] ;
+
+ if ( x == destination_x && y == destination_y ) return 0 ;
+ if ( block >= block_if ) return 1073741824.0 ;
+ if ( x < 0 || y < 0 || x >= ( int )map->width || y >= ( int )map->height ) return 1073741824.0 ;
+
+ dx = abs( destination_x - x ) ;
+ dy = abs( destination_y - y ) ;
+ return ( double )block + ( double )dx*dx + ( double )dy*dy ;
+}
+
+/* --------------------------------------------------------------------------- */
+
+/* Uso: pf_open = add(pf_open, this) ; */
+/* La lista permanecerá ordenada */
+static node * node_add( node * list, node * this )
+{
+ node * curr = list ;
+ if ( !curr )
+ {
+ this->next = NULL ;
+ return this ;
+ }
+ if ( curr->f > this->f )
+ {
+ this->next = curr ;
+ return this ;
+ }
+
+ for ( ;; )
+ {
+ if ( !curr->next )
+ {
+ curr->next = this ;
+ this->next = NULL ;
+ return list ;
+ }
+ if ( curr->next->f > this->f )
+ {
+ this->next = curr->next ;
+ curr->next = this ;
+ return list ;
+ }
+ curr = curr->next ;
+ }
+}
+
+/* --------------------------------------------------------------------------- */
+
+/* Uso: pf_open = remove(pf_open, this) ; */
+static node * node_remove( node * list, node * this )
+{
+ node * curr = list ;
+ if ( curr == this ) return this->next ;
+ while ( curr )
+ {
+ if ( curr->next == this )
+ {
+ curr->next = this->next ;
+ return list ;
+ }
+ curr = curr->next ;
+ }
+ return list ;
+}
+
+/* --------------------------------------------------------------------------- */
+
+static node * node_find( node * list, int x, int y )
+{
+ while ( list )
+ {
+ if ( list->x == ( unsigned )x && list->y == ( unsigned )y ) return list ;
+ list = list->next ;
+ }
+ return NULL ;
+}
+
+/* --------------------------------------------------------------------------- */
+/*
+static void node_reset( node * list )
+{
+ node * next ;
+ while ( list )
+ {
+ next = list->next ;
+ free( list ) ;
+ list = next ;
+ }
+}
+*/
+/* --------------------------------------------------------------------------- */
+
+static node * node_new( node * parent, int x, int y, int cost_inc )
+{
+ node * curr ;
+
+ curr = ( node * ) malloc( sizeof( node ) ) ;
+ if ( !curr ) return NULL ;
+
+ curr->x = x ;
+ curr->y = y ;
+ curr->g = ( parent ? parent->g : 0 ) + cost_inc ;
+ curr->h = heuristic( x, y ) ;
+ curr->f = curr->g + curr->h ;
+
+ curr->parent = parent ;
+ curr->next = NULL ;
+ return curr ;
+}
+
+/* --------------------------------------------------------------------------- */
+
+static void node_push_succesor( node * parent, int ix, int iy, int cost )
+{
+ node * curr, * f_op, * f_cl ;
+
+ curr = node_new( parent, parent->x + ix, parent->y + iy, cost ) ;
+ if ( curr->h > 131072 )
+ {
+ free( curr ); return ;
+ }
+
+ f_cl = node_find( pf_closed, curr->x, curr->y ) ;
+ if ( f_cl )
+ {
+ free( curr ); return ;
+ }
+
+ f_op = node_find( pf_open, curr->x, curr->y ) ;
+ if ( f_op && f_op->f <= curr->f )
+ {
+ free( curr ); return ;
+ }
+
+ /* Add to general list (used for free resources)*/
+ curr->inext = pf_all; pf_all = curr;
+
+ if ( f_op ) { pf_open = node_remove( pf_open, f_op ); } /* this node is removed but childs that referent this node as parent will be wrong */
+/* this can't be possible, previous "if ( f_cl )" abort this code -> if ( f_cl ) { pf_closed = node_remove( pf_closed, f_cl ); }*/ /* this node is removed but childs that referent this node as parent will be wrong */
+
+ pf_open = node_add( pf_open, curr ) ;
+}
+
+/* --------------------------------------------------------------------------- */
+
+static void node_push_succesors( node * parent, int options )
+{
+ node * prior = parent->parent ;
+ if ( !prior ) prior = parent ;
+
+ node_push_succesor( parent, 1, 0, prior->x < parent->x ? 9 : 10 ) ;
+ node_push_succesor( parent, 0, 1, prior->x > parent->x ? 9 : 10 ) ;
+ node_push_succesor( parent, -1, 0, prior->y < parent->y ? 9 : 10 ) ;
+ node_push_succesor( parent, 0, -1, prior->y > parent->y ? 9 : 10 ) ;
+
+ if ( !( options & PF_NODIAG ) )
+ {
+ node_push_succesor( parent, 1, 1, 12 ) ;
+ node_push_succesor( parent, -1, -1, 12 ) ;
+ node_push_succesor( parent, -1, 1, 12 ) ;
+ node_push_succesor( parent, 1, -1, 12 ) ;
+ }
+}
+
+/* --------------------------------------------------------------------------- */
+
+static int path_find( GRAPH * bitmap, int sx, int sy, int dx, int dy, int options )
+{
+ node * curr, * inext ;
+
+ startup_x = sx ;
+ startup_y = sy ;
+ map = bitmap ;
+ destination_x = dx ;
+ destination_y = dy ;
+/*
+ node_reset( pf_open ) ;
+ node_reset( pf_closed ) ;
+*/
+ /* Release all resources */
+
+ curr = pf_all;
+ while ( curr )
+ {
+ inext = curr->inext ;
+ free( curr ) ;
+ curr = inext ;
+ }
+ pf_all = NULL;
+
+ pf_open = NULL;
+ pf_closed = NULL;
+
+ if ( path_result ) { free ( path_result ); path_result = NULL; }
+ path_result_pointer = NULL;
+
+ curr = node_new( NULL, startup_x, startup_y, 0 ) ;
+
+ /* Add to general list (used for free resources)*/
+ curr->inext = pf_all; pf_all = curr;
+
+ curr->f = curr->h = 1 ;
+ pf_open = node_add( pf_open, curr ) ;
+
+ while ( pf_open )
+ {
+ curr = pf_open ;
+ pf_open = node_remove( pf_open, curr ) ;
+
+ if ( curr->x == ( unsigned )destination_x && curr->y == ( unsigned )destination_y )
+ {
+ int count = 1 ;
+
+ found = curr ;
+ while ( curr->parent )
+ {
+ count++ ;
+ curr = curr->parent ;
+ }
+
+ path_result = malloc( sizeof( int ) * 2 * ( count + 4 ) ) ;
+ if ( !( options & PF_REVERSE ) )
+ {
+ path_result_pointer = path_result + count * 2 + 1;
+ *path_result_pointer-- = -1 ;
+ *path_result_pointer-- = -1 ;
+ while ( found )
+ {
+ *path_result_pointer-- = found->y ;
+ *path_result_pointer-- = found->x ;
+ found = found->parent ;
+ }
+
+ if ( path_result_pointer != path_result - 1 )
+ {
+ path_result_pointer = NULL;
+ return 0;
+ }
+ }
+ else
+ {
+ path_result_pointer = path_result ;
+ while ( found )
+ {
+ *path_result_pointer++ = found->x ;
+ *path_result_pointer++ = found->y ;
+ found = found->parent ;
+ }
+ *path_result_pointer++ = -1 ;
+ *path_result_pointer++ = -1 ;
+ }
+
+ path_result_pointer = path_result ;
+ return 1 ;
+ }
+
+ node_push_succesors( curr, options ) ;
+
+ pf_closed = node_add( pf_closed, curr ) ;
+ }
+
+ return 0 ;
+}
+
+/* --------------------------------------------------------------------------- */
+
+static int path_get( int * x, int * y )
+{
+ if ( path_result_pointer )
+ {
+ ( *x ) = *path_result_pointer++ ;
+ ( *y ) = *path_result_pointer++ ;
+ if ( *path_result_pointer == -1 ) path_result_pointer = NULL ;
+ return 1 ;
+ }
+ return 0 ;
+}
+
+/* --------------------------------------------------------------------------- */
+
+static int path_set_wall( int n )
+{
+ if ( n >= 1 ) block_if = n ;
+ return block_if ;
+}
+
+/* --------------------------------------------------------------------------- */
+/* Funciones de búsqueda de caminos */
+
+static int modpathfind_path_find( INSTANCE * my, int * params )
+{
+ GRAPH * gpath = bitmap_get( params[0], params[1] ) ;
+ if ( !gpath || !gpath->format || gpath->format->depth != 8 ) return 0;
+ return path_find( gpath, params[2], params[3], params[4], params[5], params[6] ) ;
+}
+
+/* --------------------------------------------------------------------------- */
+
+static int modpathfind_path_getxy( INSTANCE * my, int * params )
+{
+ return path_get(( int * )params[0], ( int * )params[1] ) ;
+}
+
+/* --------------------------------------------------------------------------- */
+
+static int modpathfind_path_wall( INSTANCE * my, int * params )
+{
+ return path_set_wall( params[0] ) ;
+}
+
+/* ----------------------------------------------------------------- */
+/* exports */
+/* ----------------------------------------------------------------- */
+
+#include "mod_path_exports.h"
+
+/* ----------------------------------------------------------------- */
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-29 17:45:29 +0000