1 /*
2 * mzEstimate.c --
3 *
4 * Management of tile plane for estimation of remaining cost to completion.
5 *
6 * Contains code for building estimation plane (just prior to route), and
7 * routine for computing estimates (using the estimation plane) during routing.
8 *
9 * *********************************************************************
10 * * Copyright (C) 1988, 1990 Michael H. Arnold and the Regents of the *
11 * * University of California. *
12 * * Permission to use, copy, modify, and distribute this *
13 * * software and its documentation for any purpose and without *
14 * * fee is hereby granted, provided that the above copyright *
15 * * notice appear in all copies. The University of California *
16 * * makes no representations about the suitability of this *
17 * * software for any purpose. It is provided "as is" without *
18 * * express or implied warranty. Export of this software outside *
19 * * of the United States of America may require an export license. *
20 * *********************************************************************
21 *
22 * EXPLANATION OF ESTIMATION CODE:
23 * The purpose of the estimation code is to estimate cost to completion
24 * from any point to the destintation taking into account the need to
25 * detour around major obstactles such as subcells and fences.
26 *
27 * The estimation plane permits multiple destination area (routes are
28 * made to what ever area is easiest to reach). The mzrouter also permits
29 * multiple start points of course.
30 *
31 * To achieve this purpose, prior to beginning the search for a route an
32 * estimation plane is generated with info that allows quick estimation
33 * of cost to completion during routing.
34 *
35 * The estimation plane contains
36 * ``solid'' tiles for major obstacles (subcells and fences) and space
37 * tiles. The space tiles are split on the extensions of solid tile edges
38 * so that one can always get from a solid tile corner straight out to
39 * the next blocking solid tile along tile edges. Space tiles are also split
40 * outward in each direction from the destination point.
41 *
42 * Estimators are generated for each tile in the estimation plane that allow
43 * estimates to be made for points in that tile. An estimator consists
44 * of five numbers:
45 * (x0,y0,hcost,vcost,cost0)
46 * that are used in the following formula:
47 * EstCost = (x - x0)*hcost + (y -y0)*vcost + cost0.
48 * An estimator represents the approximate cost of a path beginning at any
49 * point (x,y) in the current tile and proceedings horizontally and then
50 * vertically
51 * (or vice versa) to the tile corner (x0,y0) and then following the cheapest
52 * path along tile-edges to a destination area. The cheapest path from
53 * (x0,y0) is precomputed and has cost cost0. Currently only
54 * tile corners (x0,y0) of the tile the estimator is attached to are used
55 * for estimators. Estimators are also generated for paths from edges of
56 * a tile straight across to the nearest dest area (with out jogs). These
57 * "straight shot" estimators have zero hcost or vcost.
58 * Several estimators are attached to each
59 * tile, and the least cost one is used for any given (x,y).
60 *
61 * The estimation plane is generated in the following steps:
62 *
63 * 1. Generate solid tiles for unexpanded subcells (if subcells
64 can not be routed across on any active layer) and fences.
65 *
66 * 2. Split space tiles along extended edges of solid tiles and
67 * destination areas.
68 *
69 * 3. Assign a horizontal and vertical cost for routing in each tile.
70 * Cost for space tiles is cost of min active route-layer, cost for
71 * solid tiles is INFINITY. (could be more sophisticated - e.g.
72 * if routing is allowed over subcells on an expensive layer.)
73 *
74 * 4. Apply djikstra's shortest path algorithm to graph whose vertices
75 * are tile-corners and whose edges are tile edges. Weight on
76 * hor edges is min hor cost of the two adjacent tiles, weight on
77 * vertical edges is min of vert costs of adjacent tiles. Djikstra's
78 * algor. computes least cost path along tile-edges to
79 * destination for all tile corners
80 * (e.g. it generates all the cost0's for the estimators).
81 *
82 * 5. Build estimators for each tile - currently one estimator is built
83 * for each corner of the tile.
84 *
85 * 6. Trim away redundant estimators - currently if an estimator e0 is
86 * always cheaper than a second e1, e1 is thrown away.
87 */
88
89 #ifndef lint
90 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/mzrouter/mzEstimate.c,v 1.2 2008/06/01 18:37:44 tim Exp $";
91 #endif /* not lint */
92
93 #include <stdio.h>
94
95 #include "utils/magic.h"
96 #include "utils/geometry.h"
97 #include "utils/geofast.h"
98 #include "tiles/tile.h"
99 #include "utils/hash.h"
100 #include "database/database.h"
101 #include "utils/signals.h"
102 #include "textio/textio.h"
103 #include "windows/windows.h"
104 #include "dbwind/dbwind.h"
105 #include "utils/malloc.h"
106 #include "utils/list.h"
107 #include "debug/debug.h"
108 #include "textio/textio.h"
109 #include "utils/heap.h"
110 #include "mzrouter/mzrouter.h"
111 #include "mzrouter/mzInternal.h"
112
113 /* largest finite tile plane coordinates, need to reduce INFINITY and MINFINITY
114 * defined in tile.h because of some funny buisness off at infinity?
115 */
116
117 /* Special case mips machines because of a compiler bug, as of 8/9/89 */
118 #ifdef mips
119 static int MAX_FINITE_COORDINATE = (INFINITY-10);
120 static int MIN_FINITE_COORDINATE = (MINFINITY+10);
121 #else
122 #define MAX_FINITE_COORDINATE (INFINITY-10)
123 #define MIN_FINITE_COORDINATE (MINFINITY+10)
124 #endif
125
126 /*----------- Vertex structure for shortest path algorithm ---------------*/
127 typedef struct vertex
128 {
129 int vx_status; /* which corner in tile, IN set when min distance
130 * to vertex determined (shortest path algor) */
131 Tile *vx_tile; /* tile vertex is attached to */
132 dlong vx_cost; /* Min cost from here to destination point */
133 } Vertex;
134
135 #define VX_CORNER 7
136 #define VX_NONE 0
137 #define VX_L_LEFT 1
138 #define VX_U_LEFT 2
139 #define VX_L_RIGHT 4
140 #define VX_IN 8
141
142 /* Estimators for estimating cost from point within tile, (x,y), along a
143 * certain path to destination.
144 *
145 * EstCost = (x - x0) * hCost + (y - y0) * vCost + cost0
146 */
147 typedef struct estimate
148 {
149 int e_x0;
150 int e_y0;
151 dlong e_cost0;
152 int e_hCost;
153 int e_vCost;
154 struct estimate *e_next;
155 } Estimate;
156
157 /* --------------- tileCosts structure --------------------------------------*/
158 /* One of these is associated with each tile in the mzEstimate plane. They
159 * are pointed to by the client fields of the tiles.
160 */
161 typedef struct tileCosts
162 {
163 int tc_hCost; /* horizontal cost / unit distance */
164 int tc_vCost; /* vertical cost / unit distance */
165 Vertex tc_vxLLeft; /* Vertices corresponding to 3 corners of this tile */
166 Vertex tc_vxULeft;
167 Vertex tc_vxLRight;
168 Estimate *tc_estimates; /* path estimates for point in this tile */
169 } TileCosts;
170
171 /*---------------- static data, local to this file --------------------------*/
172 bool mzEstimateExists = FALSE; /* Set on first call to mzBuildEstimate */
173
174 /* Forward declarations */
175 extern void mzCleanEstimate();
176 extern void mzBuildCornerEstimators();
177 extern void mzBuildStraightShotEstimators();
178 extern void mzSplitTiles();
179 extern void mzAssignVertexCosts();
180 extern void mzAddVertex();
181
182
183 /*
184 * ----------------------------------------------------------------------------
185 *
186 * mzBuildEstimate --
187 * Setup contents of Estimation plane.
188 *
189 * Results:
190 * None
191 *
192 * Side effects:
193 * Add tiles to mzEstimate plane, create a tileCost struc for each tile
194 * complete with estimates.
195 *
196 * ----------------------------------------------------------------------------
197 */
198
199 void
mzBuildEstimate()200 mzBuildEstimate()
201 {
202 /* Clear estimation plane, reclaiming storage */
203 if(mzEstimateExists)
204 {
205 mzCleanEstimate();
206 }
207 mzEstimateExists = TRUE; /* Set flag, so we know to clean next time */
208
209 /* Now build the estimate plane from scratch */
210 if(mzEstimate)
211 {
212 bool subcellsOpaque;
213
214 /* determine whether subcells can be crossed on any active layer */
215 {
216 RouteLayer *rL;
217
218 subcellsOpaque = TRUE;
219 for(rL = mzActiveRLs;
220 rL!=NULL && subcellsOpaque;
221 rL=rL->rl_nextActive)
222 {
223 if(rL->rl_routeType.rt_spacing[TT_SUBCELL] < 0)
224 {
225 subcellsOpaque = FALSE;
226 }
227 }
228 }
229
230 /* If over-the-cell routing is not possible,
231 * add a tile to the estimation plane for each unexpanded subcell.
232 *
233 * NOTE: A 0 expansion mask is special cased since
234 * the mzrouter interpets a 0 mask to mean all subcells are
235 * expanded,
236 * while DBTreeSrCells() takes a 0 mask to mean all subcells are
237 * unexpanded.
238 */
239 if(mzCellExpansionMask != 0 && subcellsOpaque)
240 {
241 int mzAddSubcellEstFunc();
242 SearchContext scx;
243
244 scx.scx_area = mzBoundingRect;
245 scx.scx_trans = GeoIdentityTransform;
246 scx.scx_use = mzRouteUse;
247
248 /* clip area to bounding box to avoid overflow during transfroms */
249 GEOCLIP(&(scx.scx_area),&(mzRouteUse->cu_def->cd_bbox));
250
251 DBTreeSrCells(
252 &scx,
253 mzCellExpansionMask,
254 mzAddSubcellEstFunc,
255 (ClientData) &mzBoundingRect);
256 }
257
258 /* If route is OUTSIDE fence, add ``fence'' tiles to estimation plane
259 * for each FENCE tile on fence plane.
260 * If route is INSIDE fence, add ``fence'' tiles for each SPACE tile on
261 * the fence plane.
262 */
263 {
264 int mzAddFenceEstFunc();
265
266 if(mzInsideFence)
267 {
268
269 DBSrPaintArea(NULL, /* no hint tile */
270 mzHFencePlane,
271 &mzBoundingRect,
272 &DBSpaceBits,
273 mzAddFenceEstFunc,
274 (ClientData) &mzBoundingRect);
275 }
276 else
277 {
278
279 DBSrPaintArea(NULL, /* no hint tile */
280 mzHFencePlane,
281 &mzBoundingRect,
282 &DBAllButSpaceBits,
283 mzAddFenceEstFunc,
284 (ClientData) &mzBoundingRect);
285 }
286 }
287 }
288
289 /* Add a tile to the estimation plane for each dest area, and cut
290 * holes at the walks leading to the dest areas
291 */
292 {
293 int mzProcessDestEstFunc();
294 SearchContext scx;
295
296 scx.scx_area = mzBoundingRect;
297 scx.scx_trans = GeoIdentityTransform;
298 scx.scx_use = mzDestAreasUse;
299
300 /* clip area to bounding box to avoid overflow during transforms */
301 GEOCLIP(&(scx.scx_area),&(mzDestAreasUse->cu_def->cd_bbox));
302
303 (void) DBTreeSrTiles(
304 &scx,
305 &DBAllButSpaceAndDRCBits,
306 0,
307 mzProcessDestEstFunc,
308 (ClientData) NULL);
309 }
310
311 /*--- Split space tiles at edges of solid tiles. ---*/
312 {
313 int mzBuildSolidsListFunc();
314 List *solidsList = NULL;
315 List *l;
316
317 /* Build list of all solid,
318 * i.e. nonspace, tiles on estimation plane. */
319 DBSrPaintArea(NULL, /* no hint tile */
320 mzEstimatePlane,
321 &TiPlaneRect, /* max paintable rect. */
322 &DBAllButSpaceBits,
323 mzBuildSolidsListFunc,
324 (ClientData) &solidsList);
325
326 /* Split tiles along perpendiculars of solid tile corners. */
327 for(l=solidsList; l!=NULL; l = LIST_TAIL(l))
328 {
329 Tile *solid = (Tile *) LIST_FIRST(l);
330 Point p;
331
332 /* lower left corner */
333 mzSplitTiles(mzEstimatePlane,&(solid->ti_ll));
334
335 /* top left corner */
336 p.p_x = LEFT(solid);
337 p.p_y = TOP(solid);
338 mzSplitTiles(mzEstimatePlane,&p);
339
340 /* top right corner */
341 p.p_x = RIGHT(solid);
342 mzSplitTiles(mzEstimatePlane,&p);
343
344 /* bottom right corner */
345 p.p_y = BOTTOM(solid);
346 mzSplitTiles(mzEstimatePlane,&p);
347 }
348
349 /* Free up solids list */
350 ListDealloc(solidsList);
351 }
352
353 /* Assign costs to tiles in estimation plane:
354 * Dest tiles - 0 cost.
355 * Space tiles - min active costs.
356 * Fence tiles - infinite cost.
357 * Subcell tiles - infinite cost.
358 */
359 {
360 int mzAssignCostsFunc();
361 TileCosts spaceCosts;
362 RouteLayer *rL;
363
364 /* set space costs to min costs of active layers */
365 spaceCosts.tc_hCost = INT_MAX;
366 spaceCosts.tc_vCost = INT_MAX;
367 for(rL = mzRouteLayers; rL!=NULL; rL=rL->rl_next)
368 {
369 if(rL->rl_routeType.rt_active)
370 {
371 if(rL->rl_hCost < spaceCosts.tc_hCost)
372 spaceCosts.tc_hCost = rL->rl_hCost;
373 if(rL->rl_vCost < spaceCosts.tc_vCost)
374 spaceCosts.tc_vCost = rL->rl_vCost;
375 }
376 }
377
378 /* visit all tiles in estimate plane attaching cost structures
379 * (including vertices) to the client fields. Horizontal and
380 * vertical costs are assigned.
381 */
382 DBSrPaintArea(NULL, /* no hint tile */
383 mzEstimatePlane,
384 &TiPlaneRect,
385 &DBAllTypeBits,
386 mzAssignCostsFunc,
387 (ClientData) &spaceCosts);
388 }
389
390 /* Apply djikstra shortest path algorithm to determine minimum costs
391 * to vertices in tile edge graph.
392 */
393 mzAssignVertexCosts();
394
395 /* Build cost estimates for each tile in estimate plane */
396 {
397 int mzBuildEstimatesFunc();
398
399 DBSrPaintArea(NULL, /* no hint tile */
400 mzEstimatePlane,
401 &TiPlaneRect,
402 &DBAllTypeBits,
403 mzBuildEstimatesFunc,
404 (ClientData) NULL);
405 }
406
407 /* Trim away redundant cost estimates on tiles */
408 {
409 int mzTrimEstimatesFunc();
410
411 DBSrPaintArea(NULL, /* no hint tile */
412 mzEstimatePlane,
413 &TiPlaneRect,
414 &DBAllTypeBits,
415 mzTrimEstimatesFunc,
416 (ClientData) NULL);
417 }
418
419 return;
420 }
421
422
423 /*
424 * ----------------------------------------------------------------------------
425 *
426 * mzCleanEstimate --
427 *
428 * Clear estimate plane and reclaim storage.
429 *
430 * Results:
431 * None
432 *
433 * Side effects:
434 * See Above.
435 *
436 * ----------------------------------------------------------------------------
437 */
438
439 void
mzCleanEstimate()440 mzCleanEstimate()
441 {
442 if (mzEstimateExists)
443 {
444 int mzReclaimTCFunc();
445
446 SigDisableInterrupts(); /* Make atomic so we don't forget to reclaim
447 * anything nor reclaim it twice.
448 */
449
450 /* visit all tiles in estimate plane reclaiming attached
451 * cost structures.
452 */
453 DBSrPaintArea(NULL, /* no hint tile */
454 mzEstimatePlane,
455 &TiPlaneRect, /* max paintable rect */
456 &DBAllTypeBits,
457 mzReclaimTCFunc,
458 (ClientData) NULL);
459
460 DBClearPaintPlane(mzEstimatePlane);
461
462 mzEstimateExists = FALSE;
463
464 SigEnableInterrupts();
465 }
466
467 return;
468 }
469
470
471 /*
472 * ----------------------------------------------------------------------------
473 *
474 * mzReclaimTCFunc --
475 *
476 * Free TileCost struc (prior to erasing old estimate plane.)
477 *
478 * Results:
479 * Returns 0 always.
480 *
481 * Side effects:
482 * Frees TileCost pointed to by client field in tile struc. Clears
483 * client field pointer - just a precaution.
484 *
485 * ----------------------------------------------------------------------------
486 */
487
488 int
mzReclaimTCFunc(tile,notUsed)489 mzReclaimTCFunc(tile, notUsed)
490 Tile *tile;
491 ClientData notUsed;
492 {
493 if (tile->ti_client != (ClientData)CLIENTDEFAULT)
494 {
495 TileCosts *tc = ((TileCosts *) (tile->ti_client));
496 Estimate *e;
497
498 /* free estimates attached to tilecosts struc */
499 for(e=tc->tc_estimates; e!=NULL; e=e->e_next)
500 {
501 freeMagic((char *) e);
502 }
503
504 /* free tilecosts struc */
505 freeMagic((char *) (tile->ti_client));
506
507 /* reset client field in tile */
508 tile->ti_client = ((ClientData) CLIENTDEFAULT);
509 }
510
511 /* return 0 - to continue traversal of old estimate plane */
512 return 0;
513 }
514
515
516 /*
517 * ----------------------------------------------------------------------------
518 *
519 * mzProcessDestEstFunc --
520 *
521 * Filter function called via DBTreeSrTiles on behalf of mzBuildEstimate()
522 * above, for each dest area in the area of interest. Searches blockage
523 * planes for dest tiles and walks under dest area and paints corresponding
524 * tiles in estimation plane.
525 *
526 * Results:
527 * Returns 0 always.
528 *
529 * Side effects:
530 * Paints into mzEstimatePlane
531 *
532 * ----------------------------------------------------------------------------
533 */
534
535 int
mzProcessDestEstFunc(tile,cxp)536 mzProcessDestEstFunc(tile, cxp)
537 Tile *tile;
538 TreeContext *cxp;
539 {
540 SearchContext *scx = cxp->tc_scx;
541 TileType type = TiGetType(tile);
542 RouteType *rT;
543 Rect r, rect;
544
545 /* Transform to result coordinates */
546 TITORECT(tile, &r);
547 GEOTRANSRECT(&scx->scx_trans, &r, &rect);
548
549 /* Grow rect by max walk size in all directions so we find walks as
550 * well as the dest area.
551 */
552 rect.r_xbot -= mzMaxWalkLength;
553 rect.r_ybot -= mzMaxWalkLength;
554 rect.r_xtop += mzMaxWalkLength;
555 rect.r_ytop += mzMaxWalkLength;
556
557 /* find route type for this dest area */
558 {
559 rT = mzActiveRTs;
560 while ((rT->rt_tileType != type) && (rT!=NULL))
561 {
562 rT = rT->rt_nextActive;
563 }
564 ASSERT(rT!=NULL,"mzAddDestTileEstFunc");
565 }
566
567 /* process dest and walk tiles below dest area */
568 {
569 int mzDestTileEstFunc();
570 TileTypeBitMask destMask;
571
572 TTMaskSetOnlyType(&destMask, TT_DEST_AREA);
573 TTMaskSetType(&destMask, TT_LEFT_WALK);
574 TTMaskSetType(&destMask, TT_RIGHT_WALK);
575 TTMaskSetType(&destMask, TT_TOP_WALK);
576 TTMaskSetType(&destMask, TT_BOTTOM_WALK);
577
578 DBSrPaintArea(NULL, /* no hint tile */
579 rT->rt_hBlock,
580 &rect,
581 &destMask,
582 mzDestTileEstFunc,
583 (ClientData) NULL);
584 }
585
586 return 0;
587 }
588
589
590
591 /*
592 * ----------------------------------------------------------------------------
593 *
594 * mzDestTileEstFunc --
595 *
596 * Paint dest area into estimate plane, or cut whole over walks.
597 *
598 * Results:
599 * Returns 0 always.
600 *
601 * Side effects:
602 * Modifies estimate plane.
603 *
604 * ----------------------------------------------------------------------------
605 */
606
607 int
mzDestTileEstFunc(tile,cdarg)608 mzDestTileEstFunc(tile, cdarg)
609 Tile *tile;
610 ClientData cdarg;
611 {
612 Rect rect;
613
614 /* set rect to bounding box of tile */
615 TITORECT(tile, &rect);
616
617 if(TiGetType(tile)==TT_DEST_AREA)
618 /* paint dest area into estimate plane */
619 {
620 DBPaintPlane(mzEstimatePlane,
621 &rect,
622 mzEstimatePaintTbl[TT_EST_DEST],
623 (PaintUndoInfo *) NULL);
624 }
625 else
626 /* cut hole for walk in estimate plane */
627 {
628 DBPaintPlane(mzEstimatePlane,
629 &rect,
630 mzEstimatePaintTbl[TT_SPACE],
631 (PaintUndoInfo *) NULL);
632 }
633
634 return 0;
635 }
636
637
638 /*
639 * ----------------------------------------------------------------------------
640 *
641 * mzAddSubcellEstFunc --
642 *
643 * Filter function called via DBTreeSrTiles on behalf of mzBuildEstimate()
644 * above, for each unexpanded subcell in the area of interest,
645 * a TT_EST_SUBCELL tile is painted on each estimate plane for
646 * the bounding box of the subcell.
647 *
648 * Results:
649 * Returns 0 always.
650 *
651 * Side effects:
652 * Paints into mzEstimatePlane
653 *
654 * ----------------------------------------------------------------------------
655 */
656
657 int
mzAddSubcellEstFunc(scx,cdarg)658 mzAddSubcellEstFunc(scx, cdarg)
659 SearchContext *scx;
660 ClientData cdarg;
661 {
662 Rect r, rDest;
663
664 /* Transform bounding box to result coords */
665 r = scx->scx_use->cu_def->cd_bbox;
666 GEOTRANSRECT(&scx->scx_trans, &r, &rDest);
667
668 /* paint subcell block onto estimate plane */
669 DBPaintPlane(mzEstimatePlane,
670 &rDest,
671 mzEstimatePaintTbl[TT_EST_SUBCELL],
672 (PaintUndoInfo *) NULL);
673
674 /* continue search */
675 return (0);
676 }
677
678
679 /*
680 * ----------------------------------------------------------------------------
681 *
682 * mzAddFenceEstFunc --
683 *
684 * Filter function called via DBSrPaintArea on behalf of mzBuildEstimate()
685 * above, for each fence tile in the area of interest,
686 * a TT_EST_FENCE tile is painted on the estimate plane for
687 * each nonspace tile on the fence plane.
688 *
689 * Results:
690 * Returns 0 always.
691 *
692 * Side effects:
693 * Paints into mzEstimatePlane
694 *
695 * ----------------------------------------------------------------------------
696 */
697
698 int
mzAddFenceEstFunc(tile,buildArea)699 mzAddFenceEstFunc(tile, buildArea)
700 Tile *tile;
701 Rect *buildArea; /* currently ignored */
702 {
703 Rect r;
704
705 /* Get boundary of tile */
706 TITORECT(tile, &r);
707
708 /* paint fence into estimate plane */
709 DBPaintPlane(mzEstimatePlane,
710 &r,
711 mzEstimatePaintTbl[TT_EST_FENCE],
712 (PaintUndoInfo *) NULL);
713
714 /* continue search */
715 return (0);
716 }
717
718
719 /*
720 * ----------------------------------------------------------------------------
721 *
722 * mzBuildSolidsList --
723 *
724 * Called by DBSrPaintArea for each solid tile in estimation plane
725 * Creates list of these tiles.
726 *
727 * Results:
728 * Returns 0 always.
729 *
730 * Side effects:
731 * Adds to list passed as arg.
732 *
733 * ----------------------------------------------------------------------------
734 */
735
736 int
mzBuildSolidsListFunc(tile,listPtr)737 mzBuildSolidsListFunc(tile, listPtr)
738 Tile *tile;
739 List **listPtr; /* pointer to list to add tile to */
740 {
741 LIST_ADD(tile,*listPtr);
742
743 /* return 0 - to continue search */
744 return(0);
745 }
746
747
748 /*
749 * ----------------------------------------------------------------------------
750 *
751 * mzAssignCostsFunc --
752 *
753 * Assigns horizontal and vertical costs to tiles in estimate plane.
754 *
755 * Results:
756 * Returns 0 always.
757 *
758 * Side effects:
759 * Adds to list passed as arg.
760 *
761 * ----------------------------------------------------------------------------
762 */
763 int
mzAssignCostsFunc(tile,spaceCosts)764 mzAssignCostsFunc(tile, spaceCosts)
765 Tile *tile;
766 TileCosts *spaceCosts; /* costs to assign to space tiles */
767 {
768 Tile *tRight, *tUp;
769 TileCosts *newCosts;
770 Vertex *v;
771
772 /* Alloc TileCosts struc for this tile, and attach it */
773 newCosts = (TileCosts *) mallocMagic((unsigned) (sizeof(TileCosts)));
774 tile->ti_client = (ClientData) newCosts;
775
776 /* Assign hor and vert costs for tile */
777 switch(TiGetType(tile))
778 {
779 case TT_EST_DEST:
780 newCosts->tc_hCost = 0;
781 newCosts->tc_vCost = 0;
782 break;
783
784 case TT_SPACE:
785 *newCosts = *spaceCosts;
786 break;
787
788 case TT_EST_FENCE:
789 case TT_EST_SUBCELL:
790 newCosts->tc_hCost = INT_MAX;
791 newCosts->tc_vCost = INT_MAX;
792 break;
793
794 default:
795 /* unrecognized tile type */
796 ASSERT(FALSE,"mzAssignCostsFunc");
797 }
798
799 /* add lower-left vertex */
800 v = &(newCosts->tc_vxLLeft);
801 v->vx_status = VX_L_LEFT;
802 v->vx_tile = tile;
803 v->vx_cost = COST_MAX;
804
805 /* add lower-right vertex, if at 'T' */
806 NEXT_TILE_RIGHT(tRight, tile, BOTTOM(tile));
807 if (BOTTOM(tRight)!=BOTTOM(tile))
808 {
809 /* lower-right vertex at 'T', so add it */
810 v = &(newCosts->tc_vxLRight);
811 v->vx_status = VX_L_RIGHT;
812 v->vx_tile = tile;
813 v->vx_cost = COST_MAX;
814 }
815 else
816 {
817 /* no 'T' */
818 newCosts->tc_vxLRight.vx_status = VX_NONE;
819 }
820
821 /* add upper-left vertex, if at 'T' */
822 NEXT_TILE_UP(tUp, tile, LEFT(tile));
823 if (LEFT(tUp)!=LEFT(tile))
824 {
825 /* upper-left vertex at 'T', so add it */
826 v = &(newCosts->tc_vxULeft);
827 v->vx_status = VX_U_LEFT;
828 v->vx_tile = tile;
829 v->vx_cost = COST_MAX;
830 }
831 else
832 {
833 /* no 'T' */
834 newCosts->tc_vxULeft.vx_status = VX_NONE;
835 }
836
837 /* initial estimates to NULL list */
838 newCosts->tc_estimates = NULL;
839
840 /* return 0 - to continue traversal of estimate plane */
841 return(0);
842 }
843
844
845 /*
846 * ----------------------------------------------------------------------------
847 *
848 * mzDestInitialAssignFunc
849 *
850 * Add one vertex of dest tile to adjacency heap to initialize graph for
851 * Djikstra's shortest path computation.
852 *
853 * Results:
854 * Returns 0 always.
855 *
856 * Side effects:
857 * Initials cost to zero and adds a vertex to adjacency heap.
858 *
859 * ----------------------------------------------------------------------------
860 */
861 int
mzDestInitialAssignFunc(tile,cdarg)862 mzDestInitialAssignFunc(tile, cdarg)
863 Tile *tile;
864 ClientData cdarg;
865 {
866 Heap *adjHeap = (Heap *) cdarg;
867 Vertex *v;
868
869 /* get lower left vertex */
870 v = &(((TileCosts *)(tile->ti_client))->tc_vxLLeft);
871
872 /* cost from dest is zero */
873 v->vx_cost = 0;
874
875 /* add vertex to adjHeap */
876 HeapAddDLong(adjHeap, 0, (char *) v);
877
878 /* return 0 - to continue search */
879 return(0);
880 }
881
882
883 /*
884 * ----------------------------------------------------------------------------
885 *
886 * mzBuildEstimatesFunc --
887 *
888 * Build path estimates for this tile.
889 * (For now builds
890 * + one estimate for each corner of the tile.
891 * + one estimate for no jog path to destination in each direction where
892 * this is possible.)
893 *
894 * Results:
895 * Returns 0 always.
896 *
897 * Side effects:
898 * Adds estimates to TileCost struc attached to tile.
899 *
900 * ----------------------------------------------------------------------------
901 */
902
903 int
mzBuildEstimatesFunc(tile,notUsed)904 mzBuildEstimatesFunc(tile, notUsed)
905 Tile *tile;
906 ClientData notUsed;
907 {
908
909 mzBuildCornerEstimators(tile);
910 mzBuildStraightShotEstimators(tile);
911
912 /* return 0 - to continue traversal of estimate plane */
913 return(0);
914 }
915
916
917 /*
918 * ----------------------------------------------------------------------------
919 *
920 * mzBuildCornerEstimators --
921 *
922 * Build path estimates for paths via corners of this tile.
923 *
924 * Results:
925 * None.
926 *
927 * Side effects:
928 * Adds estimates to TileCost struc attached to tile.
929 *
930 * ----------------------------------------------------------------------------
931 */
932
933 void
mzBuildCornerEstimators(tile)934 mzBuildCornerEstimators(tile)
935 Tile *tile;
936 {
937 TileCosts *tc = (TileCosts *) (tile->ti_client);
938 Vertex *vLLeft = NULL;
939 Vertex *vULeft = NULL;
940 Vertex *vLRight = NULL;
941 Vertex *vURight = NULL;
942
943 /* find vertex strucs corresponding to four corners.
944 * (NULL, for corners at infinity)
945 */
946 {
947 Tile *tUp, *tRight, *tDiag;
948 Tile *tRT, *tTR;
949
950 if(LEFT(tile)>=MIN_FINITE_COORDINATE)
951 {
952 if(BOTTOM(tile)>=MIN_FINITE_COORDINATE)
953 {
954 /* Lower Left */
955 vLLeft = &(tc->tc_vxLLeft);
956 }
957
958 if(TOP(tile)<=MAX_FINITE_COORDINATE)
959 {
960 /* Upper Left */
961 NEXT_TILE_UP(tUp, tile, LEFT(tile));
962 if (LEFT(tUp)<LEFT(tile))
963 {
964 /* upper-left vertex at 'T', so stored with tile */
965 vULeft = &(tc->tc_vxULeft);
966 }
967 else
968 {
969 /* no 'T', stored with tUp */
970 vULeft = &(((TileCosts *)(tUp->ti_client))->tc_vxLLeft);
971 }
972 }
973 }
974
975 if(RIGHT(tile)<=MAX_FINITE_COORDINATE)
976 {
977 if(BOTTOM(tile)>=MIN_FINITE_COORDINATE)
978 {
979 /* Lower Right */
980 NEXT_TILE_RIGHT(tRight, tile, BOTTOM(tile));
981 if (BOTTOM(tRight)<BOTTOM(tile))
982 {
983 /* lower-right vertex at 'T', so stored with tile */
984 vLRight = &(tc->tc_vxLRight);
985 }
986 else
987 {
988 /* no 'T', stored with tRight */
989 vLRight = &(((TileCosts *)(tRight->ti_client))->tc_vxLLeft);
990 }
991 }
992
993 if(TOP(tile)<=MAX_FINITE_COORDINATE)
994 {
995 /* Upper Right */
996 tRT = RT(tile); /* right top corner stitch (up) */
997 tTR = TR(tile); /* top right corner stitch (to right) */
998 if(RIGHT(tRT)>RIGHT(tile))
999 {
1000 /* upper right at 'T' stored with tTR */
1001 vURight = &(((TileCosts *)(tTR->ti_client))->tc_vxULeft);
1002 }
1003 else if (TOP(tTR)>TOP(tile))
1004 {
1005 /* upper right at 'T' stored with tRT */
1006 vURight = &(((TileCosts *)(tRT->ti_client))->tc_vxLRight);
1007 }
1008 else
1009 {
1010 /* no 'T', stored in own tile */
1011 NEXT_TILE_UP(tDiag, tTR, RIGHT(tile));
1012 vURight = &(((TileCosts *)(tDiag->ti_client))->tc_vxLLeft);
1013 }
1014 }
1015 }
1016 }
1017
1018 /* Build estimates */
1019 {
1020 Estimate *e;
1021
1022 /* Estimate for lower left corner */
1023 if (vLLeft)
1024 {
1025 e = (Estimate *) mallocMagic((unsigned) (sizeof(Estimate)));
1026 e->e_x0 = LEFT(tile);
1027 e->e_y0 = BOTTOM(tile);
1028 e->e_cost0 = vLLeft->vx_cost;
1029 e->e_hCost = tc->tc_hCost;
1030 e->e_vCost = tc->tc_vCost;
1031 e->e_next = tc->tc_estimates;
1032 tc->tc_estimates = e;
1033 }
1034
1035 /* Estimate for lower right corner */
1036 if (vLRight)
1037 {
1038 e = (Estimate *) mallocMagic((unsigned) (sizeof(Estimate)));
1039 e->e_x0 = RIGHT(tile);
1040 e->e_y0 = BOTTOM(tile);
1041 e->e_cost0 = vLRight->vx_cost;
1042 e->e_hCost = tc->tc_hCost;
1043 e->e_vCost = tc->tc_vCost;
1044 e->e_next = tc->tc_estimates;
1045 tc->tc_estimates = e;
1046 }
1047
1048 /* Estimate for upper right corner */
1049 if (vURight)
1050 {
1051 e = (Estimate *) mallocMagic((unsigned) (sizeof(Estimate)));
1052 e->e_x0 = RIGHT(tile);
1053 e->e_y0 = TOP(tile);
1054 e->e_cost0 = vURight->vx_cost;
1055 e->e_hCost = tc->tc_hCost;
1056 e->e_vCost = tc->tc_vCost;
1057 e->e_next = tc->tc_estimates;
1058 tc->tc_estimates = e;
1059 }
1060
1061 /* Estimate for upper left corner */
1062 if (vULeft)
1063 {
1064 e = (Estimate *) mallocMagic((unsigned)(sizeof(Estimate)));
1065 e->e_x0 = LEFT(tile);
1066 e->e_y0 = TOP(tile);
1067 e->e_cost0 = vULeft->vx_cost;
1068 e->e_hCost = tc->tc_hCost;
1069 e->e_vCost = tc->tc_vCost;
1070 e->e_next = tc->tc_estimates;
1071 tc->tc_estimates = e;
1072 }
1073 }
1074
1075 return;
1076 }
1077
1078
1079 /*
1080 * ----------------------------------------------------------------------------
1081 *
1082 * mzBuildStraightShotEstimators --
1083 *
1084 * Build path estimates for paths straight to dest area (no jogs)
1085 *
1086 * Results:
1087 * None.
1088 *
1089 * Side effects:
1090 * Adds estimates to TileCost struc attached to tile.
1091 *
1092 * ----------------------------------------------------------------------------
1093 */
1094 void
mzBuildStraightShotEstimators(tile)1095 mzBuildStraightShotEstimators(tile)
1096 Tile *tile;
1097 {
1098 TileCosts *tc = (TileCosts *) (tile->ti_client);
1099
1100 /* straight right */
1101 {
1102 Tile *tSolid = tile;
1103
1104 /* get first solid tile to right */
1105 while(TiGetType(tSolid)==TT_SPACE &&
1106 tSolid!=mzEstimatePlane->pl_right)
1107 {
1108 tSolid = TR(tSolid);
1109 }
1110
1111 /* if dest tile, build estimator */
1112 if(TiGetType(tSolid) == TT_EST_DEST)
1113 {
1114 Estimate *e;
1115
1116 e = (Estimate *) mallocMagic((unsigned)(sizeof(Estimate)));
1117 e->e_x0 = RIGHT(tile);
1118 e->e_y0 = 0;
1119 if (tc->tc_hCost == INT_MAX)
1120 e->e_cost0 = COST_MAX;
1121 else
1122 e->e_cost0 = (dlong) (LEFT(tSolid) - RIGHT(tile)) * tc->tc_hCost;
1123 e->e_hCost = tc->tc_hCost;
1124 e->e_vCost = 0;
1125 e->e_next = tc->tc_estimates;
1126 tc->tc_estimates = e;
1127 }
1128 }
1129
1130 /* straight left */
1131 {
1132 Tile *tSolid = tile;
1133
1134 /* get first solid tile to left */
1135 while(TiGetType(tSolid)==TT_SPACE &&
1136 tSolid!=mzEstimatePlane->pl_left)
1137 {
1138 tSolid = BL(tSolid);
1139 }
1140
1141 /* if dest tile, build estimator */
1142 if(TiGetType(tSolid) == TT_EST_DEST)
1143 {
1144 Estimate *e;
1145
1146 e = (Estimate *) mallocMagic((unsigned)(sizeof(Estimate)));
1147 e->e_x0 = LEFT(tile);
1148 e->e_y0 = 0;
1149 if (tc->tc_hCost == INT_MAX)
1150 e->e_cost0 = COST_MAX;
1151 else
1152 e->e_cost0 = (dlong) (RIGHT(tSolid) - LEFT(tile)) * tc->tc_hCost;
1153 e->e_hCost = tc->tc_hCost;
1154 e->e_vCost = 0;
1155 e->e_next = tc->tc_estimates;
1156 tc->tc_estimates = e;
1157 }
1158 }
1159
1160 /* straight up */
1161 {
1162 Tile *tSolid = tile;
1163
1164 /* get first solid tile above */
1165 while(TiGetType(tSolid)==TT_SPACE &&
1166 tSolid!=mzEstimatePlane->pl_top)
1167 {
1168 tSolid = RT(tSolid);
1169 }
1170
1171 /* if dest tile, build estimator */
1172 if(TiGetType(tSolid) == TT_EST_DEST)
1173 {
1174 Estimate *e;
1175
1176 e = (Estimate *) mallocMagic((unsigned)(sizeof(Estimate)));
1177 e->e_x0 = 0;
1178 e->e_y0 = TOP(tile);
1179 if (tc->tc_vCost == INT_MAX)
1180 e->e_cost0 = COST_MAX;
1181 else
1182 e->e_cost0 = (dlong) (BOTTOM(tSolid) - TOP(tile)) * tc->tc_vCost;
1183 e->e_hCost = 0;
1184 e->e_vCost = tc->tc_vCost;
1185 e->e_next = tc->tc_estimates;
1186 tc->tc_estimates = e;
1187 }
1188 }
1189
1190 /* straight down */
1191 {
1192 Tile *tSolid = tile;
1193
1194 /* get first solid tile below */
1195 while(TiGetType(tSolid)==TT_SPACE &&
1196 tSolid!=mzEstimatePlane->pl_bottom)
1197 {
1198 tSolid = LB(tSolid);
1199 }
1200
1201 /* if dest tile, build estimator */
1202 if(TiGetType(tSolid) == TT_EST_DEST)
1203 {
1204 Estimate *e;
1205
1206 e = (Estimate *) mallocMagic((unsigned)(sizeof(Estimate)));
1207 e->e_x0 = 0;
1208 e->e_y0 = BOTTOM(tile);
1209 if (tc->tc_vCost == INT_MAX)
1210 e->e_cost0 = COST_MAX;
1211 else
1212 e->e_cost0 = (dlong)(TOP(tSolid) - BOTTOM(tile)) * tc->tc_vCost;
1213 e->e_hCost = 0;
1214 e->e_vCost = tc->tc_vCost;
1215 e->e_next = tc->tc_estimates;
1216 tc->tc_estimates = e;
1217 }
1218 }
1219
1220 return;
1221 }
1222
1223
1224 /*
1225 * ----------------------------------------------------------------------------
1226 *
1227 * AlwaysAsGood --
1228 *
1229 * Compares two estimators.
1230 *
1231 * Results:
1232 * Returns TRUE iff est1 is always less than or equal to est2.
1233 *
1234 * Side effects:
1235 * modifies estimates list in TileCost struc attached to tile,
1236 * specifically sets floating origin coords. (Floating coords
1237 * are those with corresponding cost field of 0, hence
1238 * there value does not matter when computing estimates. They
1239 * are set here as a convience, to permit uniform treatment of
1240 * all estimators within this function.)
1241 *
1242 *
1243 *
1244 * ----------------------------------------------------------------------------
1245 */
1246
1247 bool
AlwaysAsGood(est1,est2,tile)1248 AlwaysAsGood(est1, est2, tile)
1249 Estimate *est1;
1250 Estimate *est2;
1251 Tile *tile;
1252 {
1253 if(est1->e_cost0 > est2->e_cost0)
1254 {
1255 return FALSE;
1256 }
1257 else
1258 /* check if using est1 even from est2 origin
1259 * is cheaper than using est2 */
1260 {
1261 /* If est2 x origin is floating, set to worst case */
1262 if(est2->e_hCost == 0)
1263 {
1264 est2->e_x0 = (ABS(LEFT(tile) - est1->e_x0) >
1265 ABS(RIGHT(tile) - est1->e_x0)) ?
1266 LEFT(tile) : RIGHT(tile);
1267 }
1268
1269 /* If est2 y origin is floating, set to worst case */
1270 if(est2->e_vCost == 0)
1271 {
1272 est2->e_y0 = (ABS(BOTTOM(tile) - est1->e_y0) >
1273 ABS(TOP(tile) - est1->e_y0)) ?
1274 BOTTOM(tile) : TOP(tile);
1275 }
1276
1277 /* now compute the cost from est2 origin using est1 */
1278
1279 {
1280 dlong hCost, vCost, cost;
1281
1282 if ((est1->e_hCost == INT_MAX) || (est1->e_vCost == INT_MAX))
1283 return FALSE;
1284
1285 hCost = (dlong) (est1->e_hCost *
1286 ABS(est2->e_x0 - est1->e_x0));
1287 vCost = (dlong) (est1->e_vCost *
1288 ABS(est2->e_y0 - est1->e_y0));
1289
1290 cost = hCost + vCost;
1291 cost += est1->e_cost0;
1292
1293 return (cost <= est2->e_cost0);
1294 }
1295 }
1296 }
1297
1298
1299 /*
1300 * ----------------------------------------------------------------------------
1301 *
1302 * mzTrimEstimatesFunc --
1303 *
1304 * Throw away redundant cost estimates.
1305 *
1306 * Results:
1307 * Returns 0 always.
1308 *
1309 * Side effects:
1310 * modifies estimates list in TileCost struc attached to tile.
1311 *
1312 * ----------------------------------------------------------------------------
1313 */
1314
1315 int
mzTrimEstimatesFunc(tile,notUsed)1316 mzTrimEstimatesFunc(tile, notUsed)
1317 Tile *tile;
1318 ClientData notUsed;
1319 {
1320 TileCosts *tc = (TileCosts *) (tile->ti_client);
1321 Estimate *e;
1322 Estimate *reqEstimates = NULL;
1323
1324 e = tc->tc_estimates;
1325 while(e)
1326 {
1327 Estimate *e2;
1328 bool found = FALSE;
1329
1330 /* Check if a required estimate is always as good as e */
1331 for(e2 = reqEstimates; e2!= NULL && !found; e2=e2->e_next)
1332 {
1333 if(AlwaysAsGood(e2,e,tile))
1334 {
1335 found = TRUE;
1336 }
1337 }
1338
1339 /* Check if a not-yet-processed estimate is always as good as e */
1340 for(e2 = e->e_next; e2!= NULL && !found; e2=e2->e_next)
1341 {
1342 if(AlwaysAsGood(e2,e,tile))
1343 {
1344 found = TRUE;
1345 }
1346 }
1347
1348 /* Throw away e if redundant, else save on reqEstimates list, and
1349 * continue with next unprocessed estimate.
1350 */
1351 {
1352 Estimate *eNext = e->e_next;
1353 if(found)
1354 /* Throw away */
1355 {
1356 freeMagic((char *) e);
1357 }
1358 else
1359 /* Add to required list */
1360 {
1361 e->e_next = reqEstimates;
1362 reqEstimates = e;
1363 }
1364 e = eNext;
1365 }
1366 }
1367
1368 /* save required estimate list */
1369 tc->tc_estimates = reqEstimates;
1370
1371 /* return 0 - to continue traversal of estimate plane */
1372 return(0);
1373 }
1374
1375
1376 /*
1377 * ----------------------------------------------------------------------------
1378 *
1379 * mzSplitTiles --
1380 *
1381 * Split space tiles in four directions from point - stopping at solid tiles.
1382 *
1383 * Results:
1384 * None
1385 *
1386 * Side effects:
1387 * Modifies tile structure of plane.
1388 *
1389 * ----------------------------------------------------------------------------
1390 */
1391
1392 void
mzSplitTiles(plane,point)1393 mzSplitTiles(plane, point)
1394 Plane * plane;
1395 Point * point; /* origin from which tiles split */
1396 {
1397 Tile *pointTile = TiSrPointNoHint(plane, point);
1398 Tile *t;
1399 int x = point->p_x;
1400 int y = point->p_y;
1401
1402 /* Don't split from infinite points */
1403 if(x<MIN_FINITE_COORDINATE || x>MAX_FINITE_COORDINATE ||
1404 y<MIN_FINITE_COORDINATE || y>MAX_FINITE_COORDINATE)
1405 {
1406 return;
1407 }
1408
1409 /* split tiles to right of point */
1410 {
1411 /* init t to tile to right of pointTile */
1412 NEXT_TILE_RIGHT(t,pointTile,y);
1413
1414 while (TiGetType(t)==TT_SPACE && BOTTOM(t)!=y && t!=plane->pl_right)
1415 {
1416 /* split t */
1417 t=TiSplitY(t, y);
1418
1419 /* move one tile to right */
1420 NEXT_TILE_RIGHT(t,t,y);
1421 }
1422 }
1423
1424 /* split tiles up from point */
1425 {
1426 /* init t to tile above pointTile */
1427 NEXT_TILE_UP(t,pointTile,x)
1428
1429 while (TiGetType(t)==TT_SPACE && LEFT(t)!=x && t!=plane->pl_top)
1430 {
1431 /* split t */
1432 t=TiSplitX(t, x);
1433
1434 /* move one tile up */
1435 NEXT_TILE_UP(t,t,x);
1436 }
1437 }
1438
1439 /* split tiles to left of point */
1440 {
1441 /* init t to tile to left of pointTile */
1442 NEXT_TILE_LEFT(t,pointTile,y);
1443
1444 while (TiGetType(t)==TT_SPACE && BOTTOM(t)!=y && t!=plane->pl_left)
1445 {
1446 /* split t */
1447 t = TiSplitY(t, y);
1448
1449 /* move one tile to left */
1450 NEXT_TILE_LEFT(t,t,y);
1451 }
1452 }
1453
1454 /* split tiles down from point */
1455 {
1456 /* init t to tile below pointTile */
1457 NEXT_TILE_DOWN(t,pointTile,x);
1458
1459 while (TiGetType(t)==TT_SPACE && LEFT(t)!=x && t!=plane->pl_bottom)
1460 {
1461 /* split t */
1462 t=TiSplitX(t, x);
1463
1464 /* move one tile down */
1465 NEXT_TILE_DOWN(t,t,x);
1466 }
1467 }
1468
1469 /* finally, if point is in a SPACE tile, split it in four */
1470 if(TiGetType(pointTile)==TT_SPACE)
1471 {
1472 t = pointTile;
1473 if(x != LEFT(t))
1474 {
1475 Tile *tOther = TiSplitX(t, x);
1476 if(y != BOTTOM(tOther))
1477 TiSplitY(tOther, y);
1478 }
1479 if(y != BOTTOM(t))
1480 TiSplitY(t, y);
1481 }
1482
1483 return;
1484 }
1485
1486
1487 /*
1488 * ----------------------------------------------------------------------------
1489 *
1490 * mzAssignVertexCosts --
1491 *
1492 * Applies Djikstra's shortest path algorithm to compute minimum cost to
1493 * each tile corner, assuming cost along edge is minimum of cost associated
1494 * with adjacent tiles times length of the edge. (Hor costs for hor. edges,
1495 * vertical costs for vertical edges.)
1496 *
1497 * Treats estimate plane as a graph, with tile corners as vertices and
1498 * tile edges as nodes. Weights
1499 *
1500 * Results:
1501 * None.
1502 *
1503 * Side effects:
1504 * Fills in vertex costs in strucs hanging of clientData fields of
1505 * tiles in estimation plane.
1506 *
1507 * ----------------------------------------------------------------------------
1508 */
1509
1510 void
mzAssignVertexCosts()1511 mzAssignVertexCosts()
1512 {
1513 Heap adjHeap; /* vertices adjacent to the IN set are put here */
1514 HeapEntry buf, *he;
1515 Tile *t;
1516
1517 /* Initialize Heap */
1518 HeapInitType(&adjHeap, 1024, FALSE, FALSE, HE_DLONG);
1519
1520 /* Initial at least one vertex of each dest term to zero cost and add
1521 * to adjHeap. Zero cost will be propagated to other vertices of dest
1522 * terms since hcost and vcost are 0 for dest tiles.
1523 */
1524 {
1525 int mzDestInitialAssignFunc();
1526 TileTypeBitMask destOnly;
1527
1528 TTMaskSetOnlyType(&destOnly, TT_EST_DEST);
1529
1530 DBSrPaintArea(NULL, /* no hint tile */
1531 mzEstimatePlane,
1532 &mzBoundingRect,
1533 &destOnly,
1534 mzDestInitialAssignFunc,
1535 (ClientData) &adjHeap);
1536 }
1537
1538 /* keep adding least cost ADJACENT vertex to IN until no ADJACENT vertices
1539 * left. (Vertices adjacent to the addvertex are added to adjHeap.)
1540 */
1541 while((he = HeapRemoveTop(&adjHeap,&buf))!=NULL)
1542 {
1543 Vertex *v = (Vertex *)(he->he_id);
1544 if (!(v->vx_status & VX_IN))
1545 {
1546 /* vertex not already IN, so process it */
1547 mzAddVertex(v,&adjHeap);
1548 }
1549 }
1550
1551 /* Free heap */
1552 HeapKill(&adjHeap, (void (*)()) NULL);
1553
1554 return;
1555 }
1556
1557
1558 /*
1559 * ----------------------------------------------------------------------------
1560 *
1561 * mzAddVertex --
1562 *
1563 * Subroutine of mzAssignVertexCosts.
1564 * Adds least cost vertex on adjHeap to IN set. Adds vertices adjacent to
1565 * new IN vertex to adjHeap, or adjusts there cost if they are already there.
1566 *
1567 * Results:
1568 * None.
1569 *
1570 * Side effects:
1571 * Modifies adjHeap and vertex strucs attached to tiles
1572 * on estimation plane.
1573 *
1574 * ----------------------------------------------------------------------------
1575 */
1576
1577 void
mzAddVertex(vxThis,adjHeap)1578 mzAddVertex(vxThis, adjHeap)
1579 Vertex *vxThis;
1580 Heap *adjHeap;
1581 {
1582 Tile *tThis; /* Tile vxThis is attached to */
1583 Point loc; /* location of vxThis */
1584 Tile *tLoc; /* Tile containing location of vxThis */
1585 Tile *tLeft, *tRight, *tAbove, *tBelow; /* Neighbors of tLoc */
1586
1587 /* Mark this vertex IN */
1588 vxThis->vx_status |= VX_IN;
1589
1590 /* Ignore if we're already at maximum cost */
1591 if (vxThis->vx_cost == COST_MAX) return;
1592
1593 /* compute location of this vertex, and tile containing that loc */
1594 tThis = vxThis->vx_tile;
1595 switch (vxThis->vx_status & VX_CORNER)
1596 {
1597 case VX_L_LEFT:
1598 loc.p_x = LEFT(tThis);
1599 loc.p_y = BOTTOM(tThis);
1600 tLoc = tThis;
1601 break;
1602
1603 case VX_L_RIGHT:
1604 loc.p_x = RIGHT(tThis);
1605 loc.p_y = BOTTOM(tThis);
1606 NEXT_TILE_RIGHT(tLoc, tThis, BOTTOM(tThis));
1607 break;
1608
1609 case VX_U_LEFT:
1610 loc.p_x = LEFT(tThis);
1611 loc.p_y = TOP(tThis);
1612 NEXT_TILE_UP(tLoc, tThis, LEFT(tThis));
1613 break;
1614 }
1615
1616 /* find tiles neighboring loc */
1617 NEXT_TILE_LEFT(tLeft, tLoc, loc.p_y);
1618 NEXT_TILE_RIGHT(tRight, tLoc, loc.p_y);
1619 NEXT_TILE_UP(tAbove, tLoc, loc.p_x);
1620 NEXT_TILE_DOWN(tBelow, tLoc, loc.p_x);
1621
1622 /* process adjacent vertex ABOVE */
1623 {
1624 Vertex *vxAbove;
1625 int yAbove;
1626
1627 /* Check for no edge above */
1628 if(LEFT(tLoc)!=loc.p_x)
1629 goto noAbove;
1630
1631 if(TOP(tLeft) < TOP(tLoc))
1632 {
1633 /* T from left */
1634 vxAbove = &(((TileCosts *)(RT(tLeft)->ti_client))->tc_vxLRight);
1635 yAbove = TOP(tLeft);
1636 }
1637 else
1638 {
1639 if(LEFT(tAbove)==LEFT(tLoc))
1640 {
1641 /* no T */
1642 vxAbove = &(((TileCosts *)(tAbove->ti_client))->tc_vxLLeft);
1643 yAbove = BOTTOM(tAbove);
1644 }
1645 else
1646 {
1647 /* T from bottom */
1648 vxAbove = &(((TileCosts *)(tLoc->ti_client))->tc_vxULeft);
1649 yAbove = BOTTOM(tAbove);
1650 }
1651 }
1652
1653 /* adjust cost */
1654 {
1655 int rate, distance;
1656 dlong newCost;
1657
1658 if(yAbove > MAX_FINITE_COORDINATE) goto noAbove;
1659
1660 rate = MIN(((TileCosts *)(tLoc->ti_client))->tc_vCost,
1661 ((TileCosts *)(tLeft->ti_client))->tc_vCost);
1662
1663 if(rate == INT_MAX) goto noAbove;
1664
1665 distance = yAbove - loc.p_y;
1666 newCost = (dlong) (rate * distance);
1667 newCost += vxThis->vx_cost;
1668
1669 if(newCost < vxAbove->vx_cost)
1670 {
1671 vxAbove->vx_cost = newCost;
1672 HeapAddDLong(adjHeap, newCost, (char *) vxAbove);
1673 }
1674 }
1675 noAbove:;
1676 }
1677
1678
1679 /* process adjacent vertex to RIGHT */
1680 {
1681 Vertex *vxRight;
1682 int xRight;
1683
1684 /* Check for no edge to RIGHT */
1685 if(BOTTOM(tLoc)!=loc.p_y)
1686 goto noRight;
1687
1688 if(RIGHT(tBelow) < RIGHT(tLoc))
1689 {
1690 /* T from below */
1691 vxRight = &(((TileCosts *)(TR(tBelow)->ti_client))->tc_vxULeft);
1692 xRight = RIGHT(tBelow);
1693 }
1694 else
1695 {
1696 if(BOTTOM(tRight)==BOTTOM(tLoc))
1697 {
1698 /* no T */
1699 vxRight = &(((TileCosts *)(tRight->ti_client))->tc_vxLLeft);
1700 xRight = LEFT(tRight);
1701 }
1702 else
1703 {
1704 /* T from left */
1705 vxRight = &(((TileCosts *)(tLoc->ti_client))->tc_vxLRight);
1706 xRight = LEFT(tRight);
1707 }
1708 }
1709
1710 /* adjust cost */
1711 {
1712 int rate, distance;
1713 dlong newCost;
1714
1715 if(xRight > MAX_FINITE_COORDINATE) goto noRight;
1716
1717 rate = MIN(
1718 ((TileCosts *)(tLoc->ti_client))->tc_hCost,
1719 ((TileCosts *)(tBelow->ti_client))->tc_hCost);
1720
1721 if(rate == INT_MAX) goto noRight;
1722
1723 distance = xRight - loc.p_x;
1724 newCost = (dlong) (rate * distance);
1725 newCost += vxThis->vx_cost;
1726
1727 if (newCost < vxRight->vx_cost)
1728 {
1729 vxRight->vx_cost = newCost;
1730 HeapAddDLong(adjHeap, newCost, (char *) vxRight);
1731 }
1732 }
1733 noRight:;
1734 }
1735
1736 /* For going down and to the left, we want tiles to contain their
1737 * right and upper edges. Adjust tLoc and neighbors accordingly.
1738 * The trick is to center tLoc and neighbors around loc - (1,1).
1739 */
1740 {
1741 Point locMinus;
1742
1743 /* locMinus used to get tiles for loc, that contain top and right
1744 * edges.
1745 */
1746
1747 locMinus = loc;
1748 --(locMinus.p_x);
1749 --(locMinus.p_y);
1750
1751 if(BOTTOM(tLoc)>locMinus.p_y)
1752 NEXT_TILE_DOWN(tLoc, tLoc, loc.p_x);
1753 if(LEFT(tLoc)>locMinus.p_x)
1754 NEXT_TILE_LEFT(tLoc, tLoc, locMinus.p_y);
1755
1756 /* find tiles neighboring loc */
1757 NEXT_TILE_LEFT(tLeft, tLoc, locMinus.p_y);
1758 NEXT_TILE_RIGHT(tRight, tLoc, locMinus.p_y);
1759 NEXT_TILE_UP(tAbove, tLoc, locMinus.p_x);
1760 NEXT_TILE_DOWN(tBelow, tLoc, locMinus.p_x);
1761 }
1762
1763 /* process adjacent vertex BELOW */
1764 {
1765 Vertex *vxBelow;
1766 int yBelow;
1767
1768 /* Check for no edge below */
1769 if(RIGHT(tLoc)!=loc.p_x)
1770 goto noBelow;
1771
1772 if(BOTTOM(tRight) >= BOTTOM(tLoc))
1773 {
1774 /* LowerLeft of tRight */
1775 vxBelow = &(((TileCosts *)(tRight->ti_client))->tc_vxLLeft);
1776 yBelow = BOTTOM(tRight);
1777 }
1778 else
1779 {
1780 /* T from Left */
1781 vxBelow = &(((TileCosts *)(tLoc->ti_client))->tc_vxLRight);
1782 yBelow = BOTTOM(tLoc);
1783 }
1784
1785 /* adjust cost */
1786 {
1787 int rate, distance;
1788 dlong newCost;
1789
1790 if(yBelow < MIN_FINITE_COORDINATE) goto noBelow;
1791
1792 rate = MIN(
1793 ((TileCosts *)(tLoc->ti_client))->tc_vCost,
1794 ((TileCosts *)(tRight->ti_client))->tc_vCost);
1795
1796 if(rate == INT_MAX) goto noBelow;
1797
1798 distance = loc.p_y - yBelow;
1799 newCost = (dlong) (rate * distance);
1800 newCost += vxThis->vx_cost;
1801
1802 if(newCost < vxBelow->vx_cost)
1803 {
1804 vxBelow->vx_cost = newCost;
1805 HeapAddDLong(adjHeap, newCost, (char *) vxBelow);
1806 }
1807 }
1808 noBelow:;
1809 }
1810
1811 /* process adjacent vertex to LEFT */
1812 {
1813 Vertex *vxLeft;
1814 int xLeft;
1815
1816 /* Check for no edge to Left */
1817 if(TOP(tLoc)!=loc.p_y)
1818 goto noLeft;
1819
1820 if(LEFT(tAbove) >= LEFT(tLoc))
1821 {
1822 /* LowerLeft of tAbove */
1823 vxLeft = &(((TileCosts *)(tAbove->ti_client))->tc_vxLLeft);
1824 xLeft = LEFT(tAbove);
1825 }
1826 else
1827 {
1828 /* T from Bottom */
1829 vxLeft = &(((TileCosts *)(tLoc->ti_client))->tc_vxULeft);
1830 xLeft = LEFT(tLoc);
1831 }
1832
1833 /* adjust cost */
1834 {
1835 int rate, distance;
1836 dlong newCost;
1837
1838 if(xLeft < MIN_FINITE_COORDINATE) goto noLeft;
1839
1840 rate = MIN(
1841 ((TileCosts *)(tLoc->ti_client))->tc_hCost,
1842 ((TileCosts *)(tAbove->ti_client))->tc_hCost);
1843
1844 if(rate == INT_MAX) goto noLeft;
1845
1846 distance = loc.p_x - xLeft;
1847 newCost = (dlong) (rate * distance);
1848 newCost += vxThis->vx_cost;
1849
1850 if(newCost < vxLeft->vx_cost)
1851 {
1852 vxLeft->vx_cost = newCost;
1853 HeapAddDLong(adjHeap, newCost, (char *) vxLeft);
1854 }
1855 }
1856 noLeft:;
1857 }
1858 }
1859
1860 /*
1861 * ----------------------------------------------------------------------------
1862 *
1863 * mzEstimatedCost --
1864 *
1865 * Results:
1866 * Estimated cost of route from point to destination.
1867 *
1868 * Side effects:
1869 * None.
1870 *
1871 * ----------------------------------------------------------------------------
1872 */
1873
1874 // changed from DoubleInt to dlong
1875 dlong
mzEstimatedCost(point)1876 mzEstimatedCost(point)
1877 Point *point;
1878 {
1879 Tile *t = TiSrPointNoHint(mzEstimatePlane, point);
1880 TileCosts *tc = ((TileCosts *) t->ti_client);
1881 Estimate *e;
1882 dlong bestCost;
1883
1884 bestCost = COST_MAX;
1885 for (e=tc->tc_estimates; e!=NULL; e=e->e_next)
1886 {
1887 dlong hCost, vCost, cost;
1888
1889 if (e->e_hCost == INT_MAX || e->e_vCost == INT_MAX) continue;
1890
1891 hCost = (dlong)e->e_hCost * (dlong)ABS(point->p_x - e->e_x0);
1892 vCost = (dlong)e->e_vCost * (dlong)ABS(point->p_y - e->e_y0);
1893
1894 cost = hCost + vCost;
1895 cost += e->e_cost0;
1896
1897 if(cost < bestCost)
1898 bestCost = cost;
1899 }
1900
1901 return bestCost;
1902 }
1903
1904 /*
1905 * ----------------------------------------------------------------------------
1906 *
1907 * mzDumpEstimates --
1908 *
1909 * Dump info in estimate plane (for debugging).
1910 *
1911 * Results:
1912 * None.
1913 *
1914 * Side effects:
1915 * info written to file or via TxPrintf()
1916 *
1917 * ----------------------------------------------------------------------------
1918 */
1919
1920 void
mzDumpEstimates(area,fd)1921 mzDumpEstimates(area,fd)
1922 Rect *area;
1923 FILE *fd;
1924 {
1925 int mzDumpEstFunc();
1926
1927 if(mzEstimateExists)
1928 {
1929 /* Visit each tile in the Estimate plane - dumping associated info */
1930 DBSrPaintArea(NULL, /* no hint tile */
1931 mzEstimatePlane,
1932 area,
1933 &DBAllTypeBits,
1934 mzDumpEstFunc,
1935 (ClientData) fd);
1936 }
1937 else
1938 {
1939 TxPrintf("No estimate plane!\n");
1940 TxPrintf("(Must ``:*ir deb noclean true'' and do a route first.)\n");
1941 }
1942
1943 return;
1944 }
1945
1946
1947 /*
1948 * ----------------------------------------------------------------------------
1949 *
1950 * mzDumpEstFunc --
1951 *
1952 * Filter function called via DBSrPaintArea on behalf of mzDumpEstimates()
1953 * above, for each estimate tile in the area of interest,
1954 * the info associated with each tile is dumped.
1955 *
1956 * Results:
1957 * Returns 0 always.
1958 *
1959 * Side effects:
1960 * Dumps info associated with tile.
1961 *
1962 * ----------------------------------------------------------------------------
1963 */
1964
1965 int
mzDumpEstFunc(tile,fd)1966 mzDumpEstFunc(tile, fd)
1967 Tile *tile;
1968 FILE *fd;
1969 {
1970 Rect r;
1971 TileCosts *tilec = (TileCosts *) tile->ti_client;
1972
1973 /* Get boundary of tile */
1974 TITORECT(tile, &r);
1975
1976 /* dump info, to file if provided, else to screen */
1977 if(fd)
1978 {
1979 fprintf(fd,"\ntile %p\t\t (x: %d to %d, y: %d to %d)\n",
1980 tile, r.r_xbot, r.r_xtop, r.r_ybot, r.r_ytop);
1981 fprintf(fd,"\thcost = %d ",
1982 tilec->tc_hCost);
1983 fprintf(fd,"vcost = %d \n",
1984 tilec->tc_vCost);
1985 {
1986 char str[100];
1987 Estimate *e;
1988
1989 fprintf(fd,"\tEstimates:\n");
1990
1991 for(e=tilec->tc_estimates; e!=NULL; e=e->e_next)
1992 {
1993 fprintf(fd,"\t\t%"DLONG_PREFIX"d + ABS(x - %d)*%d + ABS(y - %d)*%d\n",
1994 e->e_cost0,e->e_x0,e->e_hCost,
1995 e->e_y0,e->e_vCost);
1996 }
1997 }
1998 }
1999 else
2000 {
2001 TxPrintf("\ntile %x\t\t (x: %d to %d, y: %d to %d)\n",
2002 (pointertype) tile, r.r_xbot, r.r_xtop, r.r_ybot, r.r_ytop);
2003 TxPrintf("\thcost = %d, ",
2004 tilec->tc_hCost);
2005 TxPrintf("vcost = %d \n",
2006 tilec->tc_vCost);
2007 {
2008 char str[100];
2009 Estimate *e;
2010
2011 TxPrintf("\tEstimates:\n");
2012
2013 for(e=tilec->tc_estimates; e!=NULL; e=e->e_next)
2014 {
2015 TxPrintf("\t\t%lld + ABS(x - %d)*%d + ABS(y - %d)*%d\n",
2016 e->e_cost0,e->e_x0,e->e_hCost,
2017 e->e_y0,e->e_vCost);
2018 }
2019 }
2020 }
2021
2022 /* continue search */
2023 return (0);
2024 }
2025