jim@pcad.UUCP (James Kuzeja) (10/24/90)
I would like some advice on techniques for handling the interaction of two objects, or in general, n objects, whose exact types are not known until run time. I have provided a quite lengthy example of the problem, but it boils down to this: How can the useful abstraction supplied by virtual functions be extended to interactions of several objects? The premise is this: I need to determine if two shapes intersect. Of course, the exact type of shape is not known at compile time, and extensibility of the shape class is a must. So far, my solution has been to establish several conventions that new shapes must follow to allow intersection tests to work. The first is that a new shape must provide methods for determining if it intersects any existing shape (including itself). The second is that it must provide methods (which are "keyed" with a protected enum) that are sufficient to allow future shapes to determine intersections. All shapes are derived from a common class Shape. It is NOT desirable to derive each new shape from the preceding shape (too many wasted data members). Thus, all derived shapes are in a brother-sister relationship, not parent-child. Here is an example: typedef int Boolean; typedef int Vector; typedef int Coord; // dummy types class Shape { public: // The next member function reverses the input args. // With message passing, I think this would solve my problem, as // after two reversals, both shape types would be "known". virtual Boolean hit (const Shape &x) const { return x.hit(*this); } virtual Draw () const = 0; protected: enum ShapeKey { key }; // allow children to share "secrets" }; class Circle : public Shape { Vector _center; Coord _radius; public: // handle intersections for all existing shapes (Circle) Boolean hit (const Circle &x); Draw(); // allow ONLY brothers to access internals Vector center(ShapeKey x) { return _center; } Coord radius(ShapeKey x) { return _radius; } }; class Box : public Shape { Vector _lowerleft; Vector _upperright; public: // handle intersections for all existing shapes (Circle, Box) Boolean hit (const Circle &x); Boolean hit (const Box *x); Draw(); // allow ONLY sisters to access internals Vector lowerleft(ShapeKey x) { return _lowerleft; } Vector upperright(ShapeKey x) { return _upperright; } }; My original thinking was this: to intersect shape C (a circle) with shape B (a box), while not knowing either type (because they were in a list of Shapes, for instance), call C.hit(B) . This would resolve to Circle::hit (const Shape &B) . This then calls B.hit (const Circle &(*this)) , [and *this == C], which resolves to Box::hit (const Circle &C) <=== WRONG! (but what I expected). The last statement won't work because Box::hit (const Circle &C) is not virtual. So, here are my options as far as I and my colleagues have been able to determine: 0) Whenever a new shape is added, go back to all the other shapes and teach them how to intersect with the new shape. I am only stating this for completeness. If I wanted to do this, I would be using C, not C++. 1) Whenever a new shape is added (e.g., Polygon), derive it from the last defined shape, and add a virtual function to intersect with each existing shape (including itself). This is unacceptable, because there would be too much unused data space in objects at the end of the hierarchy. 2) Whenever a new shape is added, modify the base Shape class to contain a virtual "hit" function that takes the new shape type as an argument. This also is unacceptable, because it would require a recompile of the shape library, and this would not be feasible for most library users. Also, it seems to go against the grain of "virtual-ness". 3) All shapes could be required to produce a common, say polygonal, representation of themselves for purposes of intersection. This is unacceptable, because too much precision would be lost by using polygonal approximations of the actual shape. However, this technique might be applicable in other circumstances. 4) Provide an "is-a" member function for each shape. Only use this to resolve the type of the second argument. If the type is recognized, handle the intersection; otherwise, reverse the arguments and recall the function. The newer shape should always recognize the older shape. One implementation: typedef int Boolean; typedef int Vector; typedef int Coord; // dummy types class Shape { public: virtual int IsA () const = 0; virtual Boolean hit (const Shape &x) const = 0; virtual void Draw () const = 0; protected: enum ShapeKey { key }; // allow children to share "secrets" }; const int SH_CIRCLE = 0; // avoid enums here - not extensible class Circle : public Shape { Vector _center; Coord _radius; public: int IsA() const { return SH_CIRCLE; } // handle intersections for all existing shapes (Circle) Boolean hit (const Shape &x) const { switch (x.IsA()) { case SH_CIRCLE: return hit((Circle &)x); break; // ugh! default: return x.hit(*this); break; // try other shape } } Boolean hit (const Circle &x); void Draw(); // allow ONLY sisters to access internals Vector center(ShapeKey x) const { return _center; } Coord radius(ShapeKey x) const { return _radius; } }; const int SH_BOX = SH_CIRCLE + 1; // avoid enums here - not extensible class Box : public Shape { Vector _lowerleft; Vector _upperright; public: int IsA() const { return SH_BOX; } // handle intersections for all existing shapes (Circle, Box) Boolean hit (const Shape &x) const { switch (x.IsA()) { case SH_CIRCLE: return hit((Circle &)x); break; // ugh! case SH_BOX: return hit((Box &) x); break; // ugh! default: return x.hit(*this); break; // try other shape } } Boolean hit (const Circle &x); Boolean hit (const Box *x); void Draw(); // allow ONLY brothers to access internals Vector lowerleft(ShapeKey x) const { return _lowerleft; } Vector upperright(ShapeKey x) const { return _upperright; } }; (Another implementation could use arrays of function pointers in each class, and index them with the IsA function result.) In either case, the IsA function is a kludge at best. However, this solution DOES allow extension without recompilation. I would appreciate any thoughts on this problem, as well as the multiple- unknown-interacting-objects problem in general. I would also appreciate references to treatments of this topic in the literature. Thanks. Jim Kuzeja Personal CAD Systems Voice: (508) 692-8843 One Technology Park Drive FAX: (508) 692-9261 Westford, MA 01886